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

Is B context free? Please explain in detail.

asked in Theory of Computation by Junior (617 points) | 204 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

answered by Junior (889 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



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

44,235 questions
49,718 answers
163,885 comments
65,834 users