0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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^*$. $\endgroup$
    – collapsar
    Commented Mar 19, 2014 at 11:05

1 Answer 1

3
$\begingroup$

$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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Commented Mar 19, 2014 at 14:58
  • $\begingroup$ @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 ... $\endgroup$
    – collapsar
    Commented Mar 19, 2014 at 15:30
  • $\begingroup$ @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. $\endgroup$
    – collapsar
    Commented Mar 19, 2014 at 15:35
  • $\begingroup$ you're right, I should have written $\{a^nb^m\}, n < m$, rather than $\{a^nb^n\}$. I got them mixed up. $\endgroup$ Commented Mar 19, 2014 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .