345 views
Is the language L = {$a^nb^m : n = 2^m$} context-free?

i think No

its CSL.
Can u explain????

@Gateasp2020

@Satbir

For each $n$ we first have to compute $log \ m$  and then we need to print the sequence. For computing $log \ m$ we need a tape. Hence it is $CSL$

By using PDA-stack we can pop logn-a’s on reading each m b’s, right?

So it means this is CFL..?

Considering m=2 gives n=4;

 a a a a Z

On completion of input string reading, we’re only left with Z(top of stack)….so this is CFL

Correct me if Im wrng ;)

by

The language L = {a^nb^m : n =2^m} can be shown to not be context-free by using the pumping lemma for context-free languages.

The pumping lemma states that if a language L is context-free, then there exists a number p (the pumping length) such that any string s in L of length greater than or equal to p can be divided into three substrings x, y, and z such that:

1. |xy| <= p
2. |y| > 0
3. for all i >= 0, xy^i z is in L

Let's take the string "a^4b^2" which is in the language L.

We can divide the string into x = "a^2", y = "a^2", z = "b^2"

Now we can pump y any number of times to get "a^4b^2, a^6b^2, a^8b^2,..."

All of these new strings generated by pumping y are not in the language L because n is not equal to 2^m, which breaks the rule of the language L.

Therefore, we can conclude that the language L = {a^nb^m : n =2^m } is not context-free.

by

1 vote