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

Is B context free? Please explain in detail.

in Theory of Computation by (443 points) | 224 views
+3
B) is not CFL...
+1
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.
0
B is CSL??
0
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)
+1
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)
0
What about 'a'?

When a is push or pop?
+1

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

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

'a' input symbol. In option B as per your answer.

Related questions

+2 votes
2 answers
5
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,288 questions
55,719 answers
192,113 comments
90,125 users