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

84 views

### Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?

At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the ...
602 views

### Show that language generated by grammar is regular

We have grammar with nonterminals $X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t$ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k$ How can I show that ...
195 views

### Show that a language cannot be generated by linear grammar

I have a language $L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$ that is a language with even number of b's. I found a grammar for it with these rules: $S \rightarrow aS \ | \ bL \ | \ \lambda$...
83 views

### Finding the language generated for CFG

What language generated by the following context-free grammar 1) S------> SaS | b i already know the answer to question one but to prove it would is be something like this: S -----> SaaS -----> baab ...
I am doing an exercise from Models Of Computation - Ch - 5, Q-1(r). Design a grammar that generates this context-free language $\{ x\space\$\space y^R \,|\, x, y \in\{0, 1\}^* \text{ and } x \ne y\}...