0
$\begingroup$

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

enter image description here

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

enter image description here

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ This question asks us to grade your answers. This is your TA's job rather than the goal of this site. $\endgroup$
    – Yuval Filmus
    Commented Jan 26, 2017 at 7:43

3 Answers 3

Reset to default
1
$\begingroup$

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\}$$

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Jan 26, 2017 at 7:42
  • $\begingroup$ I sensed as much, whence I avoided giving full answers. And yes, a comment would've been enough. $\endgroup$
    – Kai
    Commented Jan 26, 2017 at 9:19
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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