Question

Use CFG or PDA to prove L= {0^a1^b0^c : b ≠ a + c; a, b, c ≥ _0} is a context-free language. Please add your explanation, thank you.

If you can use the theorem(union of CFL and regular language = CFL) is also welcomed.

Answer 1

A language L is context-free if ∃ CFG G : L(G) = L

Give a CFG for L =  {0^a1^b0^c : b ≠ a + c; a, b, c ≥ _0}

L says some of an's ought to be equivalent to some of b's. Their link says the first number of an's ought to be equivalent to the quantity of b's. In this way, we can make a PDA which will initially push for a's, fly for b's. So it very well may be acknowledged by pushdown automata, consequently setting free.

Sol:- Let L is context free. Then, L must satisfy pumping lemma. At first, choose a number n of the pumping lemma. Then, take z as 0ⁿ1ⁿ2ⁿ.

G = (V, Σ, R, S) with set of variables V = {S, X}, where S is the start variable; set of terminals Σ = {a, b, c}; and rules S → aSc | X X → bXc | ε