1
$\begingroup$

This question already has an answer here:

I don't want to create a duplicate question of How to prove a language is regular?, I only want to know what is a good and simple way to explain why a language like

$\qquad \displaystyle L = \{w \in \{a,b,c\}^* \mid w = ua \text{ and } |u| \equiv 2 \pmod 3 \}$.

is regular.

$\endgroup$

marked as duplicate by D.W., Luke Mathieson, David Richerby, Raphael Apr 14 '15 at 9:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Construct an automaton accepting this language. There is an NFA with 4 states and a DFA with 6 states. $\endgroup$ – Yuval Filmus Apr 13 '15 at 22:19
  • 2
    $\begingroup$ I understand you didn't want to create a duplicate, but the way to explain why that language is regular is answered in that question, so I think this does count as a duplicate. If you don't think your question is answered by that question, then please edit the question to explain why none of the answers there address your question, so the community can form their own judgement. $\endgroup$ – D.W. Apr 13 '15 at 23:19
  • 1
    $\begingroup$ Because $L$ is the concatenation of $\{u\in \{a,b,c\}^*\mid |u|\equiv2\pmod3\}$ and the language $\{a\}$. It shouldn't be too hard to show that both languages are regular (perhaps by constructing FAs for each). $\endgroup$ – Rick Decker Apr 13 '15 at 23:58
  • 1
    $\begingroup$ What's the difference between "explain why $L$ is regular" and "prove that $L$ is regular"? A proof is just a convincing explanation. $\endgroup$ – David Richerby Apr 14 '15 at 7:38
1
$\begingroup$

The easiest way is by giving a regular expression for $L$: $$ L = (a+b+c)^2((a+b+c)^3)^*a. $$ Here $(a+b+c)^2$ is a shorthand for $(a+b+c)(a+b+c)$, and $(a+b+c)^3$ is a shorthand for $(a+b+c)(a+b+c)(a+b+c)$.

Other ways described in the comments:

  1. Give a DFA (6 states) or an NFA (4 states) for $L$.
  2. Decompose $L = L' a$ and give a DFA (3 states) or an NFA (3 states) for $L'$.
$\endgroup$

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