Question

Let L = {aⁱ b^j c^k | i, j,k > 0 and (i = j or i = k)}. On the board is the beginning of an NPDA that recognizes the language. Complete the NPDA using just three more states.

Answer 1

Answer-

First method-

L = {ai bj ck | i, j,k > 0 and (i = j or i = k)}
Grammar for language L

G = (V, Σ, P, S)

where
V = {S, A,B,C,D},
Σ = {a, b, c}; and rules

P={ S → AB | C , A → aAb | ε , B → cB | ε , C → aCc | D , D → bD | ε }

S is the start variable

CFG to PDA -

Let G=(V, Σ, P, S) be a context free grammar, we can design a PDA corresponding to given CFG as
PDA (A)=({q},∑,δ, Γ,q,Z,F)
q-state
∑-input symbol
δ-transition function
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 Σ.
Γ-stack symbols
q-initial state
Z-initial stack symbol
F-final state

Grammar G = (V, Σ, P, S)

where
V = {S, A,B,C,D},
Σ = {a, b, c}; and rules

P={ S → AB | C , A → aAb | ε , B → cB | ε , C → aCc | D , D → bD | ε }

S is the start variable

PDA corresponding to given CFG
PDA(A)=({q1,q2,q3},{a, b, c},δ,{a, b, c,S, A,B,C,D},{q1},{S},{q3})
where
q0 -{q1}
∑-{a, b, c}
Γ-Stack symbols {a, b, c,S, A,B,C,D}
qf - {q3}
Z-{S}- starting symbol of stack
Where δ is defined by the following rules
R0:δ(q1, ε,ε)={(q2,S$)
R1:δ(q2, ε,S)={(q2,AB),(q2,C)}
R2:δ(q2, ε,A)={(q2,aAb),(q2,ε)}
R3:δ(q2, ε,B)={(q2,cB),(q2,ε)}
R4:δ(q2, ε,C)={(q2,aCc),(q2,D)}
R5:δ(q2, ε,D)={(q2,bD),(q2,ε)}
R6:δ(q2, a,a)={(q2,ε)}
R7: δ(q2, b,b)={(q2, ε)}
R8:δ(q2, c,c)={(q2, ε)}
R9:δ(q2, ε,$)={(q3, ε)}

State diagram- E,E → S$ £$ → E 91 92 ɛ, SAB £, SC £,A+Ab £,A → £, BB £,B► £,C+aCc ɛ, CD E,D - D £,D → a,a → bb → CC →

Second method (Where number of states is more)-

L = {abck | i, j, k > 0, and(i = j or j = k)} PDA(A)={{q1,92,93,94,95,96,97,98},{a,b,c},8,{a, b},{q1},{$},{q4,98}) where 40-{q1} E-{a,b,c} T-Stack symbols {a,b} qf - {94,98} Z-{$}- starting symbol of stack 8- is defined as 8(q1,£,£)={(92,$),(95,$)} 8(92,a,ą)={(92,a)} 8(92,5,8)={(q3,8)} 8(93,b,a)={(93,)} 8(93,ɛ,$)={(94,)} 8(94,C,E)={(94,)} 8(q5,,ɛ)={(95,ɛ)} 8(95,£,£)={(96,)} 8(96,b,ɛ)={(96,b)} 8(96,£,£)={(97,ɛ)} 8(97,c,b)={(97,)} 8(97,8,$)={(98,)} a, e a b, a +8 C, E +€ E, E e, $ + € 42 93 E, E + $ €, E + $ q5 E, E 97 96 + 6 E, E + E 98 e, $ a, eta b, € + b c, b + €