1
$\begingroup$

I have a question about the following problem:

Prove that the language $\{a^nva^n | v \in \Sigma^*, n \ge 1\}$ is regular over $\Sigma = \{a,b\}.$

I know that in proving a language is regular I can either construct a DFA, give a regular expression or show the Nerode-Relation has finite index.

My main problem is, that I cannot understand why this should be a regular language, since $\{a^nb^n | n \ge 1\}$ is not regular and of similar form. Also, I do not understand how a DFA should recognize the same amount of a's at the front and at the end of a word.

$\endgroup$
  • 3
    $\begingroup$ It doesn't have to make sure there are the same number of $a$ at both ends. Sufficient that there is one. Nothing says $v$ can't start or end with an $a$. $\endgroup$ – rici Feb 12 at 21:56
2
$\begingroup$

You can always take $n = 1$ for any string in your language...

$\endgroup$
  • 1
    $\begingroup$ I'd swear there's an old question related to this, but a cursory search didn't find it. Nice answer in any case. $\endgroup$ – Rick Decker Feb 13 at 0:49
  • 1
    $\begingroup$ @RickDecker The site is full of slight variants of these questions. I just answered a similar one earlier today. $\endgroup$ – Aaron Rotenberg Feb 13 at 2:58
  • $\begingroup$ Such "languages that look non-regular" are all over the place. Nice exercises to keep students on their toes thinking what the language is instead of just going by superficial characteristics like "there are some exponents in the description, so it's non-regular", or "words composed with some repeating parts, must be non-regular". $\endgroup$ – vonbrand Feb 15 at 15:54
  • $\begingroup$ Shortly after I posted this question I had the same thought. If you are new to the topic of formal languages then such exercises cause you a headache. Anyway, thank you for your answer. $\endgroup$ – LeoMinor Feb 19 at 14:16

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.