63 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 ...
1k 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 ...
606 views

54 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 ...
48 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? ...
35 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 ->...
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: ...
21k views

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 25k 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 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 ... 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 ... 2answers 5k views ### Prove correctness of DFA ending with ab I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts \{wab \mid w\in \{a,b\}^*\} I know that I need to prove by induction ... 3answers 1k 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 ... 1answer 3k 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|... 1answer 1k views ### PDA or CFG for language L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\} Can someone help with this L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\} 1answer 2k views ### Is the language of all non-palindromes context-free? Is the language L = \{ w \mid w \in (a,b)^* \wedge w \text{ is not a palindrome} \}, context-free? I think this grammar:  S \rightarrow aSa \mid bSb \mid aAb \mid bAa\\ A \rightarrow aAa \mid bAb \... 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 ... 1answer 2k views ### Why is the language of even-length non-palindromes context-free? We know L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\} is a context-free language. Can anyone help me produce a PDA or give me any hint how I can quickly understand why ... 2answers 250 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, ... 1answer 2k views ### Describing language generated by grammar S -> aSb | A | B A -> aS | a B -> Sb | b is this the language generated by this CFG? Or am I missing something? 1answer 892 views ### Proving grammar only generate strings that is multiple of 3 Hello I have an exercise for homework and I was hopping to get some hints in order to solve it. num-> 11 | 10 num' 01 | num 0 | num num num'-> 00 num' | 1 num' | ε I need to prove that my ... 1answer 584 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 ... 2answers 746 views ### Finding Language of a CFG Say you are given the following CFG G:$$ S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon  What is $L(G)$? ...
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 ...
### Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof
Im having a lot of trouble proving that for the Regular expression $R_{1} = \left( a^{*} b^{*} \right)^{*}$ and $R_{2} = \left( a+b \right)^{*}$ that $L \left( R_{1} \right) = L \left( R_{2} \right)$. ...