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.

Improve this question
$\endgroup$
1
  • 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, 2020 at 21:56

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 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, 2020 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, 2020 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, 2020 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, 2020 at 14:16

Your Answer

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

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