Prove or disprove that the language $L_1 = \{a^nb^m \mid n < m \}$ is regular

2,316

$L_1$ is not regular.

Assume it was. Consider a recognizing DFA with $k_0$ states. On one hand it will recognize $a^{k_0}\, b^{k_0+1}$. Operating on any input with prefix $a^{k_1}\; \text{for some}\; k_1 \leq k_0$, it will visit a state twice. Therefore by the pumping lemma, any $a^{q*k_1}\,b^{k_0+1}, q \in \mathbb{N^+}$ will be recognized, notably $a^{(\lceil\frac{k_0}{k_1}\rceil + 1)* k_1}\, b^{k_0+1}$, a contradiction.

Share:
2,316
Guildenstern
Author by

Guildenstern

Updated on March 20, 2020

Comments

  • Guildenstern
    Guildenstern over 3 years

    I have possible strategy for a proof that it is not regular. I am wondering if it is valid.

    Step 1: Prove that the language $L_2 = \{a^nb^n\}$ is not regular (for example with the Pumping Lemma).

    Step 2: Assume that $L_1$ is regular.

    Step 3: $L_3 = L_1^c$ (complement of $L_1$)

    Step 4: Since regular languages are closed under complement, $L_3$ must be regular. Since $L_2 \not\subseteq L_1$ (the $n < m$ condition), then $L_2 \subseteq L_3$. So the non-regular language $L_2$ is a subset of a $L_3$, a language that we had to conclude was regular, a contradiction.

    P.S: Maybe I could have used the Pumping Lemma on $L_1$, but I wasn't sure how I could prove that for any possible pumping of the language, since it seems that you can indeed pump as many b's as you want, though maybe I have misunderstood something about the lemma.

    • collapsar
      collapsar over 9 years
      your conclusion $L_2 \not\subseteq L_1 \rightarrow L_2 \subseteq L_3$ seems flawed. the crucial property is that $L_2 \cap L_1 = \emptyset$. Otherwise, $L_2$ might not be a subset of either set. more important, a non-regular language can perfectly well be a subset of a regular one - actually that holds for all non-regular languages, as they are subsets of $\Sigma^*$.
  • Guildenstern
    Guildenstern over 9 years
    So you use the fact that n in $\{a^nb^n\}$ is unbounded, yet you have to visit a finite number of states in order to process the $n$ $a$'s (assuming $L_1$ is regular). So then you pick that finite number of states $k_0$ which recognizes $\{a^{k_0}b^{k_0}\}$, assert that there must be a $k_1 > k_0$ s.t. $\{a^{k_1}b^{k_1}\}$ ($n$ is unbounded). So then the only way that this can be true is if the DFA visits a state more than once when processing $\{a^{k_1}b^{k_1}\}$, in which case the Pumping Lemma must hold for this transition of states, which leads to a contradiction. Is that correct?
  • collapsar
    collapsar over 9 years
    @Guildenstern I'm arguing for $\{a^nb^m\}, n<m, \,\text{rather than}\, \{a^nb^n\}$. My $k_0$ is the trivial upper bound for the number of steps between 2 consecutive visits to the same state in some recognizing DFA (let these visits occur at steps $t_1,t_2 (\text{note}\, k_1 = t_2 - t_1$). DFAs do not have memory therefore inputs $a_0 ... (a_{t_1} ... a_{t_2})^r ... a_{\_}$ produce the same result for each $r \in \mathbb{N^+}$. Basically, this is the pumping lemma for regular languages rephrased. So you will have inputs $a^{n_0}b^m, a^{n_1}b^m, \,n_0 < m < n_1$ indistiguishable to the DFA ...
  • collapsar
    collapsar over 9 years
    @Guildenstern ... This is the contradiction as only one of these inputs belongs to $L_1$. Intuitively, detecting $L_1$ requires counting. the only way for a DFA to count is by means of its states. The number of states is finite, however, therfore the dfa cannot properly 'count' for inputs exceeding a certain length.
  • Guildenstern
    Guildenstern over 9 years
    you're right, I should have written $\{a^nb^m\}, n < m$, rather than $\{a^nb^n\}$. I got them mixed up.