Question

Let L = {aibjbjai:i, j 1}. Examples of strings in L include abbbba and aabbbbbaa. Prove that L is context-free by informally describing a PDA that recognizes this language.

Answer 1

Answer-

A language is context-free grammar iff there exists a pushdown automaton recognizes the context free grammar.
L={{aibjbjai:i, j >=1}
Context free grammar for language L
G=(V,∑,P,S)
V={S,A}
∑={a,b}
P={S → aSa, S →A, A→bAb, A →bb }
S={S}
CFG to PDA Conversion-
Procedure-
Let G=(V,∑,P,S) be a context free grammar, we can construct a PDA corresponding to given CFG as
PDA (A)=({q},∑,δ, Γ,q,Z,ϕ)
Where δ is defined by the following rules
R1: δ(q, λ,A)={(q,α)|for all A→α is in P}
R2: δ(q, a,a)={(q, λ)} for each terminal a in T

Grammar G=(V,∑,P,S)
V={S,A}
∑={a,b}
P={S → aSa,S →A,A→bAb,A →bb }
S={S}
PDA corresponding to given CFG
PDA(A)=({q},{a,b},δ,{a,b,S,A},{q},{S},{ϕ})
where
q-{q}
∑-{a,b}
Γ-Stack symbols {a,b,S,A}
q-{q}
Z-{S}-starting symbol of grammar will become starting symbol of stack
Where δ is defined by the following rules
R1: δ(q, λ,S)={(q,aSa),(q,A)}
R2:δ(q, λ,A)={(q,bAb),(q,bb)}
R3: δ(q, a,a)={(q, λ)}
R4:δ(q, b,b)={(q, λ)}

Input-abbbba
δ(q, abbbba,S)
Rule R1|-δ(q, abbbba,aSa)
Rule R3|-δ(q, bbbba,Sa)
Rule R1|-δ(q, bbbba,Aa)
Rule R2|-δ(q, bbbba,bAba)
Rule R4|-δ(q, bbba,Aba)
Rule R2|-δ(q, bbba,bbba)
Rule R4|-δ(q, bba,bba)
Rule R4|-δ(q, ba,ba)
Rule R4|-δ(q, a,a)
Rule R3|-δ(q,λ ,λ)
The string abbbba accepted by PDA. Therefore language   L is context-free describing a PDA that recognizes this language.