The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

Is B context free? Please explain in detail.

in Theory of Computation by (443 points) | 224 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 (907 points)
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.

Related questions

+2 votes
2 answers
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
50,309 questions
55,747 answers
90,537 users