1
$\begingroup$

I understand why L2 is not a regular language. We can use the pumping lemma to prove it

In the case of L2:

assume n = 1 and string = ab

We assume that L2 is regular, so it has "pumping length" property and it can be divided into 3 strings, x = empty string, y = a, z = b

Now we pump y, so after pumping once we get the string: aab. Now trivially the string aab is not present in the language L2

Now let's prove why L1 is regular language:

We cannot use the pumping lemma to prove that a language is regular. To prove that a language is regular we have to build either FA or Regular expression. Right?

But i don't understand why L1 would be regular, like there will be a case where n will be equal to m, which means it resembles the string from L2, and since we know any string of the form L2 is not regular. How could we come to the conclusion that L1 regular?

We def could build a regex for L1: a * b * which means it indeed is regular. But still for some reason i cannot grasp the concept intuitively. Can someone help me please?

$\endgroup$
1
  • $\begingroup$ $L_1$ is not regular. The regex $a^*b^*$ does not guarantee that a word $a^nb^m$ will verify $m\geqslant n$. $\endgroup$
    – Nathaniel
    May 7 at 18:55

1 Answer 1

1
$\begingroup$

The language $L_1 = \{a^n b^m: n, m \ge 0, m \ge n\}$ is not regular. This can be proved using the pumping lemma.

By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$ such that if $s \in L_1$ and $|s| \ge p$, then $s$ can be divided into three pieces as $s=xyz$ such that (1) $xy^iz \in L_1, \forall i \ge 0$, (2) $|y| \ge 1$, and (3) $|xy| \le p$. Let $s=a^p b^p$. Then, $s \in L_1$ and $|s| \ge p$. Regardless of how $s$ is partitioned as $s=xyz$, since $|xy| \le p$, $y$ must contain only $a$'s. Since $y$ contains at least one $a$, $xyyz$ contains more $a$'s than $b$'s, whence $xyyz \notin L_1$. This contradicts (1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.