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$
  • $\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 Mar 19 '14 at 11:05
2
$\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$
  • $\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$ – Guildenstern Mar 19 '14 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 Mar 19 '14 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 Mar 19 '14 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$ – Guildenstern Mar 19 '14 at 15:59

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.