Finite State Automaton Language

We're given these two finite state machines where the alphabet consists of ${a, b, c}$. The question is to determine the language for the following two machines. I tried following the machines to find the language, but the languages I derived are quite verbose.

FSA #1

This FSA accepts words with at least one a followed by zero or more b's or words with at least one a followed by zero or more b's followed by at least one c.

FSA #2

This FSA accepts words with at least one a followed by at least one b or words with at least one a followed by at least one b followed by one c.

I tried converting these FSAs to regular expressions and found that my solutions hold up, but I'm wondering if there is a more concise way to explain the language of each FSA. My language explanations seem quite verbose, so any help would be appreciated.

Finite state automatons recognize regular languages. The advantage of regular languages is that it is usually trivial to express them formally.

FSA #1

$$L(M_1) = \left\{ a^kb^lc^m | k > 0, l \geq 0, m \in \{ 0, 1 \} \right\}$$

FSA #2

$$L(M_2) = \left\{ a^kb^lc^m | k > 0, l > 0, m \in \{ 0, 1 \} \right\}$$

You could be more precise by stating "This FSA accepts a word if, and only if, ...". You could be more concise by using the word "optional" in the "...".

• This might work better as a comment. Perhaps you could provide one or more full solutions for one of the two problems. Also, we usually don't answer such questions, which require grading somebody's work. Commented Jan 26, 2017 at 7:42
• I sensed as much, whence I avoided giving full answers. And yes, a comment would've been enough.
– Kai
Commented Jan 26, 2017 at 9:19

The regular expressions corresponding to your descriptions are as follows.

FSA #1

$$a^{*+1} b^* + a^{*+1} b^* c$$

... which can be simplified to

$$a^{*+1} b^* (\epsilon + c)$$

... or, in John Conway's notation

$$a^{*+1} b^* c^{\le 1}$$

We can describe this as

• one or more $a$s, followed by ...
• any number of $b$s, followed by ...
• a possible $c$.

FSA #2

$$a^{*+1} b^{*+1} + a^{*+1} b^{*+1} c$$

... which can be simplified to

$$a^{*+1} b^{*+1} (\epsilon + c)$$

... or, in John Conway's notation

$$a^{*+1} b^{*+1} c^{\le 1}$$

We can describe this as

• one or more $a$s, followed by ...
• one or more $b$s, followed by ...
• a possible $c$.

You can see that these correspond to @still_learning's prescriptions.