Identify the Nature of the given Language

30 Views Asked by At

If I am true then following two languages are not equal:-

$L_1 = \{(a^nb^m)^l / n,m,l \geq 1 \}$

$L_2 = \{(a^*b^*)^*\}$

And I think $L_1$ is not $CFL$, because suppose a case where I put $n=2$, $m = 3 $ and $ l = 100$, then each and every time when $aabbb$ occurs we have to check whether $n_a = 2 \text{ and } n_b = 3$, which I think is not possible with one stack.

1

There are 1 best solutions below

0
On

Your intuition about $L_1$ is correct, but your argumentation is not. Any fixed string by itself is a regular language. So the string you provide can be recognized by a finite automaton. The problem here is that there is an infinite variety of strings of that nature.

The most common way to prove that $L_1$ is not context-free is probably the pumping lemma. If the pumping constant for $L_1$ is $k$, you can use the word $(a^kb^k)^2$.

And since $L_2$ is by definition regular, this also shows that the two languages are not equal.