## How can I create the context free grammar for this language? [duplicate]

I need help finding the context-free grammar for this language.

$$L = \{a^ib^jc^k \in \{a,b,c\}^* \mid \text{ i,j,k \geq 1 , and i=j or i=k or both}\}.$$

I’ve found a way to satisfy $$i = j$$ or $$i = k$$ or both, and $$i,j,k \ge 0$$.

But I am lost at the $$i,j,k \ge 1$$ part. Any tips or help would be greatly appreciated.

## How to calculate the redundancy of a language [closed]

I’m trying to calculating the unicity distance for a cipher applied to a language I wrote and I’m having trouble understanding the concept of redundancy in a language.

From this book

The redundancy of a language severely reduces the amount of information conveyed with each character and the rate of a language is defined as the average number of bits of information contained in each character of a message, i.e. H(X)/N where N is the number of characters in the message.

You need to generate a frequency table for a language to calculate H(X) but an accurate frequency table requires a long message. Won’t this cause all redundancies to tend towards 0 since N can be arbitrarily long? How exactly is the redundancy for English, 1 to 1.5 given by this book, calculated? What value of N do they use?

## Context-free grammar for language involving multiplication

I’m struggling to find the context-free grammar for the following language: $$L = \{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\}$$ Any help would be appreciated.

## Prove the following language is regular?

Assume $$L_1$$ is a regular language, and define:

$$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$

Show that $$L$$ is regular.

I first tried to prove by showing that the pumping lemma holds true, then learned that it was not a double implication and can only be used to prove languages are not regular.

Then I tried to draw an NFA, but didn’t make any progress.

What’s a good way to prove that a language like this is regular?

## how would i go about giving a context free grammar of a language

I need to give a context free grammar for this language: how would i go about doing this?

{x E {d,f,#}^* | x = u#v with v = v^R for any u,v E {d,f}^*} E = Element

## Proving a language is not regular using Myhill Nerode Theorem

Let $$L = \{\alpha\in\{a,b,c\}^{*} \mid \alpha \text{ is palindrome}\}$$, show that $$L$$ is not regular using Myhill-Nerode relation.

I don’t know how to show that $$L$$ has infinite equivalence classes because $$\alpha$$ is a palindrome. I tried to use something like this, but I don’t know if its correct:

$$\alpha \equiv_{L} \beta \iff \alpha (aba)^k \in{L} \iff \beta (aba)^k \in{L}$$ $$\forall k \in \mathbb N$$ which implies that for every k there exists an equivalence class because the repetition of aba k times.

## What is the earliest use of the “this” keyword in any programming language?

I understand the this (or self or Me) is used to refer to the current object, and that it is a feature of object-oriented programming languages. The earliest language I could find which has such a concept was Smalltalk, which uses self but was wondering where and when (which programming language) the concept was first implemented?

## What are the terminals, non-terminals and set of production rules for the following language of valid first order formula?

variables: w x y z constants: C D predicates: P[2] Q[1] equality: = connectives: \land \lor \implies \iff \neg quantifiers: \exists \forall formula: \forall x ( \exists y ( P(x,y) \implies \neg Q(x) ) \lor \exists z ( ( (C = z) \land Q(z) ) \land P(x,z) ) ) 

How would I go about deriving the set of terminals, non-terminals and production rules for this language of valid First order formula?

A method to derive the solution would be more appreciated than just the solution.

## Prove that a language is regular

I’m working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible to remove zero or more symbols from w so that just the string x remains. For example, the following strings can all be obtained from 0110 by deleting symbols:

λ, 0, 1, 00, 01, 10, 11, 010, 011, 110, and 0110.

Let Σ = {0, 1} and let A ⊆ Σ ∗ be an arbitrarily chosen regular language.

Define B = {x ∈ Σ ∗ | there exists a string w ∈ A such that x is obtained from w by deleting symbols}.

In words, a string is in B if you can obtain that string by first choosing a string from A and then deleting zero or more symbols from that chosen string. Prove that B is regular.

I’m not able to prove it. Any help would be appreciated.

## give a short high level proof if the statement is true. “If A is nonregular, then there exists a nonregular language B such that A ∩ B is finite.”

I feel that the statement is true. I want to prove it. but I don’t know from where should I start. Any help would be appreciated.