Linked Questions
68 questions linked to/from How to show that L = L(G)?
28
votes
4answers
24k 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 } ...
26
votes
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 ...
7
votes
3answers
2k 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 ...
5
votes
1answer
4k views
Equivalence of two context free grammars [for the given example]
I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck:
G1:
S->e|aB|bA
B->bS|...
5
votes
1answer
197 views
Proof by induction over rules for mutually recursive relations
Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified):
$\...
4
votes
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 ...
4
votes
2answers
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 ...
4
votes
1answer
743 views
Finding the language of a context-free grammar?
Given following question:
Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start
variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $...
4
votes
3answers
280 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}...
3
votes
2answers
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 ...
3
votes
2answers
343 views
Figuring out the language of a non-linear CFG
I have the CFG G with the following production rules:
$$
S \to aSaS \mid b
$$
Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
2
votes
3answers
2k views
Why is the distinction between linear and context-free grammars useful?
The linear grammar is a grammar that's either left, right or left and right linear.
The context-free grammar can contain any kind of productions of non-terminals and terminals.
All linear grammars ...
2
votes
2answers
462 views
Proof for BFS and DFS equivalence
I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases.
Let $G$ be a directed ...
2
votes
1answer
85 views
Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL
I'm trying to prove $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL.
Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$.
Now I want to show ...
2
votes
2answers
69 views
Interpreting a Language
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 >...