# Linked Questions

70 questions linked to/from How to show that L = L(G)?
2answers
7k 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 ...
2answers
2k views

### Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
1answer
2k 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 ...
1answer
739 views

Given that I have the grammar $\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$, how am I supposed to prove that $\qquad\displaystyle S(G1) ... 2answers 161 views ### Gyorgy E. ReveszExercise 1.1: Show the grammar$G$generates the language$L$[duplicate] The exercise says "Show that the grammar$G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$generates the language$L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$." Now, I'm new to ... 0answers 435 views ### Proof of completeness for CFG having twice as many zeroes as ones [duplicate] One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ... 1answer 117 views ### How do I get and/or verify a formal Grammar for a given formal Language? [duplicate] I was given the Language$L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$and I'm supposed to find a Grammar that generates that Language. After some trying and fiddling I found one that I ... 0answers 85 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 ... 0answers 63 views ### How i can use Mathematical induction to prove CFG production? [duplicate] If I have production$G_nS \rightarrow A_i b_i \quad$for$1 \le i \le nA_i \rightarrow a_j A_i \mid a_j\quad$for$1 \le i$and$i \ne j$Prove$G_n$is sub-productions from$2n^2 - n$... 1answer 51 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? ... 0answers 37 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 ->... 0answers 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: ... 4answers 26k views ### How to prove that a grammar is unambiguous? My problem is how can I prove that a grammar is unambiguous? I have the following grammar:$$S → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ... 2answers 35k views ### How to prove that a language is context-free? There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ... 3answers 3k views ### Context-free grammar for$L = \{a^{2^k}, k \in\mathbb{N}\}$In an exercise, I am asked to find a context free grammar for language$L = \{a^{2^k}, k \in \mathbb{N}\}$. I have been trying to use a "doubling" variable. If$a^{2n} \in L, n\in\mathbb{N}\$ then use ...

15 30 50 per page