Awesome q2a theme
0 votes
I understand that the language L = {a^m b^n c^k|(m=n)or(n=k)} is CFL because it can be represented as the union of L1 = {a^m b^m c^k} and L2 = {a^m b^k c^k} which are both CFL's. But I can't figure out the working of the PDA accepting L. To check (m=n), first of all m a's will be pushed then on every occurance of b, one a will be popped out. If stack becomes empty then b's will be pushed. After this either stack will be empty meaning (m=n) or (m-n) a's or (n-m) b's will remain in the stack meaning (m!=n). How can we check for (n=k) now?
in Theory of Computation by (25 points)
edited by | 39 views

1 Answer

+1 vote
Best answer

The given language is a non-deterministic Context free language, so we can make a N-PDA(Non-Deterministic PDA) for the given language.(A deterministic push down automata will not be possible). 

I tried to make one, hope it helps. 

If we transition to state 1 it will accept the strings of type $a^{n}b^{n}c^{m}$

It we transition to state 3 it will accept the strings of type $a^{m}b^{n}c^{n}$

As transition towards 1 or 3 is not deterministic therefore it is a non-deterministic PDA.

by (525 points)
selected by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,105 questions
3,156 answers
95,955 users