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

### Proving that a word is *not* generated by a context-free grammar

I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF... How did they get the answer so that ab ...
6k 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 ...
69 views

I'm having trouble understanding some language notation, primarily what rules I can take away from it. The language is as follows: \qquad L = \{a^n b^m b^p c^p b^{n-m} \mid n > 0, m < n, p >... 2answers 32k 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 ... 1answer 2k views ### Is my proof for a context free language correct? Same number of a's as b's I have the following grammar G: \begin{align*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align*} I am going to prove that this language L(G) consists of words with the ... 3answers 278 views ### Designing a CFG that produces as many c's as the difference of numbers of a's and b's The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}...
If I have production $G_n$ $S \rightarrow A_i b_i \quad$ for $1 \le i \le n$ $A_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$ ...
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 } ...