Question

Provide an informal description and state diagram of pushdown automata for the following languages, with the alphabet {a, b}

A) {w | w = (a^i)(b^j) where i > j > 0}

B) {w | w contains an even number of b's}

C) {w | (a^k)bbb(a^k) where k >= 0}

D) {w | w=(b^k)a(b^k)(a^j)(b^j) where j, k >= 0}

Answer 1

Solution of A) : Push all a's onto stack and then pop one a for each b. If there is at least one a on stack then the string will be accepted.

Solution of B) : There has to be one b for each b. i.e when a comes as input symbol do not perform any operation and when b comes as input symbol, push it first time and pop it second time.

Solution of C) push all a's onto stack first. Then count 3 b's and then pop one a for each input symbol a.

Solution of D) : Initially push all b's onto stack. One a is seen as input symbol, start pop operation for each b as input string. pop one b for each input symbol b. Then count number of a's and number of b's using stack. If at the end there is no symbol on stack and no input symbol remains then accept the string.

If you have any doubts, you can ask in comment section.