62 questions linked to/from How to show that L = L(G)?
5k views

### Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
1k views

### Proving correctness of a CFG by induction on length of strings generated [duplicate]

Consider the following grammar with starting symbol of $S$. $$S \rightarrow 0S11\;|\;S1\;|\;0$$ Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all ...
572 views

54 views

### A context free grammar for the language of even-length non-palindromes [duplicate]

I am trying to find a context free grammar for the language $L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$ where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible ...
48 views

### Tools or techniques for studying the language a CFG produces? [duplicate]

When developing a CFG, I find that one can be confused about whether the grammar is correct, i.e. whether it recognizes only the required strings and not other strings. But this can be hard to see? ...
35 views

### Context Free Grammar for a language [duplicate]

I have a language L = {a^n b^m c^k | n = m or m != k} When I was working the problem out this is what I got: S -> S1|S2 S1 -> AC A -> aAb|$\lambda$ C -> Cc |$\lambda$ S2 -> BD B -> aB|$\lambda$ D ->...
22 views

### Grammar that generates a language with more “a” than “b” [duplicate]

I need to find a grammar that generates the language composed by all words that have more $a$ than $b$ given an alphabet $\{a,b\}$ I tried the following production rules: ...
21k views

182 views

284 views

### Prove the equivalence between a CFG and a Context free language

I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules: $S\rightarrow a^2Tb$ $T\rightarrow a^3Tb^2 |\epsilon$ are equivalent to each other. I'm ...
261 views

### Why is this language not context free?

I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not ...
221 views

### Prove L = L(R) based on a regular expression

I'm given the following language: L = {w∈{0,1}* | w ends in 010 and contains 011} The task is to find a regular expression R that describes this language and ...
153 views

### A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...