62 questions linked to/from How to show that L = L(G)?
97 views

### Proving that L(G) is the language defined by the CFG G

I have a context-free grammar defined by the production S: S → aSbS ∣ bSaS ∣ ε I need to prove that the CFG "G" can be defined as a language L(G) where L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}. ...
53 views

859 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 ...
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: ...
1k 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 ...
2k 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|...
182 views