Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)

Question

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

Comments

i think No

its CSL.

---

Can u explain????

@Gateasp2020

---

@Satbir

please explain this

---

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$

Answer 1

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 ;) 

Answer 2

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.