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

4 Comments

i think No

its CSL.
1
1
Can u explain????

@Gateasp2020
0
0

@Satbir

please explain this

0
0
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$
3
3

2 Answers

0 votes
0 votes

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

0 votes
0 votes

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.

Related questions