The Gateway to Computer Science Excellence
+2 votes

Is B context free? Please explain in detail.

in Theory of Computation by | 250 views
B) is not CFL...
B is non CFL since when the number of comparision b/w  a and c is finishing machine forget what is n and we cannot compare the number of d.
B is CSL??
In option B,we can't push c on top of a's to compare with d^2n,since we have to compare a^n to c^n(c's will pop a's and leaving d^2n to compare with nothing,with 1 stack it is not possible)
B is not cfl

D is not cfl because we have to compare n with m also after n,2n

1 Answer

–1 vote

Yes B is CFL because for a push operation for b by pass for c push and then for d pop two times hence empty stack got

by Junior
What about 'a'?

When a is push or pop?

option A is regular language in this it also be cfl push and pop not apply

And who will ensure #a=#c?
I am not talking about option A.

'a' input symbol. In option B as per your answer.
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
52,223 questions
59,811 answers
118,087 users