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.

$\endgroup$
  • $\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 Jan 26 '17 at 7:43
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\}$$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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