63 questions linked to/from How to show that L = L(G)?
120 views

### $L = \{ w \in \{0, 1, 2\}^*: |0| + |2| = |1| \}$ where |0| denotes number of 0s in the string w

I have come up with: S→0SX | 1SY | 2SZ | SS | ϵ X→1 Y→0 | 2 Z→1 I think I am wrong. Any directions?
112 views

### Language of CFG: $S \to aS | aSbS | \varepsilon$

I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of$w$has at least as many$a$'s as$b$'s} \}$.I ...
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?
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 ->...
296 views

### Prove the equivalence between a CFG and a Context free language

I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules: $S\rightarrow a^2Tb$ $T\rightarrow a^3Tb^2 |\epsilon$ are equivalent to each other. I'm ...
135 views

### Regular Expression for All strings which contain no runs of a's of length greater than two.On L={a,b,c} [closed]

My attempt is We can fairly easily build an expression containing no a, one a, or one aa: (b+c)(€+a+aa)(b+c) but if we want to repeat this, we need to be sure to have at least one non-a between ...
232 views

### Prove L = L(R) based on a regular expression

I'm given the following language: L = {w∈{0,1}* | w ends in 010 and contains 011} The task is to find a regular expression R that describes this language and ...
584 views

86 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 ...
161 views

### Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...

15 30 50 per page