Question

Give a CFG and (natural) PDA for the language { aⁱ b^j c^k e^f: i + j = k + f, i, j, k, f ≥ 0 }

Answer 1

CFG (context-free grammar) for the language  { a^ i b^ j c ^k | i, j, k ≥ 0 and i + j = k } is :

G = (V, Σ, R, S)

set of variables V = {S, X}, where S is the start variable;

set of terminals Σ = {a, b, c};

rules S → aSc | X X → bXc | ε

PDA (Pushdown Automata) for the language { a^ i b^ j c ^k | i, j, k ≥ 0 and i + j = k }:

For every a and b read in the first part of the string, the PDA pushes an x onto the stack. Then it must read c for each x out of the stack.

We show the PDA as a 6-tuple (Q, Σ, Γ, δ, q1, F), where

Q = {q1, q2, . . . , q5}

Σ = {a, b, c}

Γ = {x, $} (use $ to bottom of stack)

Transition function δ : Q × Σε × Γε → P(Q × Γε) is as follows:

Input	a	b	c	ε
Stack	X            $           ε	X            $           ε	X            $           ε	X            $           ε
q1				{(q2, $)}
q2	{(q2, x)}			{(q3, ε )}
q3		{(q3, x)}		{(q4, ε )}
q4			{(q4, ε )}
q8				{(q5, ε )}

Blank entries are ∅.

q1 is the start state

F = {q5}

Similarly, write for the given language with small changes as follows: