# 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.

• This question asks us to grade your answers. This is your TA's job rather than the goal of this site. – Yuval Filmus Jan 26 '17 at 7:43

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. – Yuval Filmus Jan 26 '17 at 7:42
• I sensed as much, whence I avoided giving full answers. And yes, a comment would've been enough. – Kai Jan 26 '17 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.