Linked Questions

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 ...

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 } ...

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 ...

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|...

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): $\...

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 ...

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}...

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 $...

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 ...

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, ...

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 ...

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 ...

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 ...

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 ...

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 >...