67 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 ...
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 29k 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 255 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 } ...