10
$\begingroup$

I took my theory of computation exams a few weeks ago, and this was one of the questions:

Assume language $L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$

Is L regular? If yes provide a regular expression or an automaton for it.

After I briefly asked him the answer after the exam, it appears it really is regular (I believe he said the expression is the simple $(a^*b^*)^*$). However I cannot seem to understand why that is. The way I see it, its concatenating $a^nb^m$ r times, like this:

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$,

which isn't regular since there is no way for an automaton to recall n and m every time. Where am I at fault here?

EDIT: I talked to the professor again, he admitted it was a mistake. The language is indeed not regular.

Improve this question
$\endgroup$
5
  • 14
    $\begingroup$ You should ask your teacher whether the language $L$ is the same as the language $K = \lbrace a^{n_1} b^{m_1} a^{n_2} b^{m_2} \cdots a^{n_r} b^{n_r} \mid r \geq 0, a_1, \ldots, a_r \geq 0, b_1, \ldots, b_r \geq 0\rbrace$. If he says "yes" then tell him I told you his question was ill-formed. $\endgroup$
    – Andrej Bauer
    Commented Oct 1, 2012 at 13:12
  • 1
    $\begingroup$ That seems the only way it could be regular, and in fact this is what I originally hastily thought and actually considered (ab)*, but then erased it realising the n and m stay the same (or should..), and gave a pumping lemma disproval for r=2, saying the same applied for bigger r (probably not exactly a complete solution either but it seems to be in the right direction). Needless to say, i got 0 for that question. I will try contacting him. $\endgroup$
    – Exci
    Commented Oct 1, 2012 at 13:18
  • $\begingroup$ I would certainly understand the question the way you did initially. $\endgroup$
    – Andrej Bauer
    Commented Oct 1, 2012 at 14:10
  • $\begingroup$ See here for more ways to show that a language is not regular. $\endgroup$
    – Raphael
    Commented Oct 2, 2012 at 17:44
  • $\begingroup$ you could also prove the same with the help of pumping lemma $\endgroup$
    – SAHIL THUKRAL
    Commented Mar 13, 2017 at 10:54

3 Answers 3

Reset to default
10
$\begingroup$

The language $L$ is not regular, as can be proved using Nerode's method. Consider the following words $w_n = a^n b$ for $n \in \mathbb{N}$. Then $w_n^2 \in L$, but for $n \neq m$, $w_n w_m \notin L$. Hence any automaton for $L$ must be in a different state after reading each $w_n$, which contradicts its finiteness.

Improve this answer
$\endgroup$
0
4
$\begingroup$

In your comment you hint that you (quote) "gave a pumping lemma disproval for $r=2$, saying the same applied for bigger $r$".

This can indeed be formalized by applying a closure property. The regular languages are closed under intersection. So if $L$ is regular, then so would be $L\cap a^*ba^*b = \{ a^n b a^n b \mid n\ge 0\} $, effectively setting $r=2$ and $m=1$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Dear reader, please don't take away "if $L$ is not regular, then neither is $L' \supset L$" here -- because that's just false! $\endgroup$
    – Raphael
    Commented Mar 13, 2017 at 22:30
  • 1
    $\begingroup$ @Raphael Right. So the correct implication would be "if $L\cap R$ is not regular, then neither is $L$", where $R$ is regular. $\endgroup$
    – Hendrik Jan
    Commented Mar 14, 2017 at 1:28
  • 1
    $\begingroup$ Of course. I was concerned that novices might read "effectively setting ..." and apply this without using closure properties. $\endgroup$
    – Raphael
    Commented Mar 14, 2017 at 8:10
0
$\begingroup$

The language: {(anbm)r | n,m,r≥0} is not regular, because while the automaton/machine reads the first sequence of letters 'a' and then letters 'b', it needs to count the number of times it read the letter 'a' and the number of times it read the letter 'b' in the first sequence to know the value of n and m.

If r>1 then another same sequence of letters 'a' and letters 'b' is expected.

If the automaton/machine doesn't know how many letters 'a' and letters 'b' it read in the first sequence then it also doesn't know the value of n and m and thus it can't tell if the other sequences from second to last are words that equal to the first sequence.

But it's known that only Turing machine can count and know the values of n and m and recognize the language above, so not just that the language above isn't regular, but even it also isn't context free, i.e. also doesn't exist pushdown automaton to recognize this language and doesn't exist context free grammar that each word derived from that context free grammar is in the above language.

Because the fact that both deterministic finite automaton and pushdown finite automaton can't count and know the values of n and m, unlike Turing machine, they can't recognize the above language and thus the above language isn't context free and isn't regular.

Counterexample to the assumption that the language above is regular:

For n=3 ∧ m=5 ∧ r=2, the following word is in the above language:

aaabbbbbaaabbbbb

But the following word isn't in the language:

aaabbbbbaaaaabbb, because does not exist n,m and r so:

(anbm)r=aaabbbbbaaaaabbb, because to satisfy the first sequence of letters 'a' and then letters 'b', must be true that n=3 ∧ m=5, and because that we see 2 sequences of letters 'a' and then letters 'b', then r=2, but if n=3 ∧ m=5 ∧ r=2 then (anbm)r = (a3b5)2 = (aaabbbbb)2 = aaabbbbbaaabbbbb ≠ aaabbbbbaaaaabbb, because their suffixes are different, i.e. aaabbbbb ≠ aaaaabbb, although their prefixes are equal to aaabbbbb for r=1.

The "best" deterministic finite automaton that can be built for this language is the deterministic finite automaton that recognizes the regular expression (a*b*)*, but it doesn't recognize the above language, because it tells that both the words aaabbbbbaaabbbbb and aaabbbbbaaaaabbb are in the language and this is not true, because aaabbbbbaaabbbbb is in the language, but aaabbbbbaaaaabbb isn't in the language.

Even pushdown finite automaton can't tell if both words are in the language or not, so only Turing machine can.

In the second sequence, the Turing machine found that n=5 ∧ m=3 and this contradicts that in the first sequence it found that n=3 ∧ m=5, so it tells that the second word isn't in the language, but no contradiction is found in the first word.

Both sequences satisfy that n=3 ∧ m=5, so the Turing machine says that the first word is in the language.

Only Turing machine can, if it counts and remembers the values of n and m by writing their value on it's tape and later read them.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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