in Theory of Computation
284 views
0 votes
0 votes
X belongs to {a,b}* such that n(a)<n(b)<2n(a) is a CFL.

Please somebody explain the push and pop sequences of the alphabets on the stack. I'm not being able to visualise, how it is CFL?
in Theory of Computation
284 views

1 comment

The first thing you should keep in mind that its non deterministic CFL and not deterministic CFL (former is more powerful)

How push pop is performed?

push all a's. Then we have to pop one a after seeing n(a) to 2* n(a) (exact number is depends on string, this is the why there is non determinism).

For example, w= abb

push a then pop one a for two b.

w= aabbb.

pop one a for first two b then one a for last b.

If w = aab

It wouldn't be accepted as for first b we can pop one a but then we are left with no b but stack isn't empty.
0
0

Please log in or register to answer this question.

Related questions