1

From what I understood, a L is regular if you can draw a FSA or a Regex. For the L={$a^n b^2 a^n | n≥0$}, I've written out a Finite State Automata and a Regex. I'm not sure if this is correct, so can someone verify this for me?

enter image description here

$ stands for epsilon by the way.

Regex: aba

Thank you!

Brian M. Scott
  • 616,228
ano
  • 37

1 Answers1

1

A good rule of thumb to determine whether a language is regular or not is if it requires counting. To form a valid string, your automaton would have to count the number of $a$'s it is adding after the two $b$'s, so that it matches the same number of $a$'s at the start. That is why it is not regular, because FSAs/regular expressions cannot count.

As mentioned in the comments, you can verify that this language is not regular formally using the pumping lemma.

The next level up from FSAs are push-down automata. A push-down automaton can (sort of) count, since it would use a stack to keep track of the number of $a$'s. This means that it is at least a deterministic context-free language.

Luke Collins
  • 8,748
  • I've just tried to prove it is not a regular language by using the pumping lemma. I've taken the pumping length to be 7, so my string would look like this

    aaaaaaabbaaaaaaa

    The part that I am unsure of is the 'cases' part during the division into xyz. Do I have to take case 1:y contains 'a', case 2:'b', case 3: 'ab' and case 4: 'ba'?

    Then I prove that it is not a regular language, by saying that i=2, which gives me for example the string: aaaaaaabbbaaaaaaa with the case 2. because this string is not part of L. Is this the correct way? Thank you for taking the time to answer!

     – ano Apr 08 '20 at 21:58
  • If this is incorrect, do I have to ignore $b^2$ in the proof of the pumping Lemma regarding the division into xyz? – ano Apr 08 '20 at 22:00
  • @ano you can not define the pumping length when using the pumping lemma to prove a language non-regular. – vonbrand Apr 09 '20 at 09:52
  • @ano vonbrand is right, see how you should use the lemma in the "use of the lemma" section of the wikipedia article. The example there is identical to yours, minus the two $b$'s in the middle. – Luke Collins Apr 09 '20 at 10:26
  • I just read the article and there are a few things that i am confused about:

    The constant P, how do you determine how long it is? and how do you know $a^p b^p$ is longer than p?

     – ano Apr 09 '20 at 10:42