Did I find the right expression for the regular language for this FSA?

174 Views Asked by At

I have the following FSA, and the regular language that I found for it:

enter image description here

Is this language correct? It doesn't match the solution in the book, but my teacher says there can be multiple equally correct languages. The book's solution looks like this: $(0\cup1)1^{*}00^{*}(11^{*}00^{*})^{*}$. Are these two languages equal?

2

There are 2 best solutions below

0
On BEST ANSWER

Yes, they are. You can simplify both to $$\Sigma^+\mathtt{0}$$ for $\Sigma = \{\mathtt{0},\mathtt{1}\}$, that is, $$(\mathtt{0}\cup\mathtt{1})(\mathtt{0}\cup\mathtt{1})^*\mathtt{0}$$

The crucial part is to observe that, after you cleared the initial state (i.e. read the first symbol), whatever you do, and wherever you are, after reading symbol $\mathtt{0}$ you get to the accepting state.

The difference between your solution and the solution from your book is that

  • you split the final loop into two cases: either you read $\mathtt{11}^*\mathtt{0}$ or a bunch of $\mathtt{0}$'s;
  • your book joins them saying that after reading $\mathtt{11}^*\mathtt{0}$ you are to to read all the $\mathtt{0}$'s left.

These are equivalent because both are in a loop, i.e. $B^*(ABB^*)^* = (AB \cup B)^*$.

I hope this helps $\ddot\smile$

0
On

Here is one calculation (inspired by dtldarek's comment):

Let $S_k$, $k=0,1,2$ represent the states above.

We have the equations $S_1 = (0|1) \big | S_1 1 \big | S_2 1$, $S_2 = S_1 0 \big | S_2 0 $.

Solving for $S_2$ gives $S_2 = S_1 0 0^*$, then $S_1 = (0|1) \big | S_1 1 \big | S_1 0 0^* 1$, which reduces to $S_1 = (0|1) (1 | 0 0^* 1)^*$, and so $S_2 = (0|1) (1 | 0 0^* 1)^* 0 0^*$.

Since $0 0^* = 0^* 0$, this gives $S_2 = (0|1) (1 | 0 0^* 1)^* 0^* 0$.

Note that $(1 | 0 0^* 1)^* = ((0|1)^* 1) \big | \epsilon$, that is, the empty string and all strings ending in $1$. Then we have $(1 | 0 0^* 1)^* 0^* = (0|1)^*$, which gives $S_2 = (0|1)(0|1)^* 0$

Now consider $R=(0|1) 1^* 0 0^* (1 1^* 0 0^*)^* = (0|1) 1^* 0^* 0 (1 1^* 0^* 0)^* = (0|1) (1^* 0^* 0 1)^* 1^* 0^* 0 $. We have $(1^* 0^* 0 1)^* = ((0|1)^* 01 )\big | \epsilon$, that is, the empty string and all strings ending in $01$. Note that $1^*0^*$ describes the set of strings that have no $0 \to 1$ transition, and so we have $(1^* 0^* 0 1)^* 1^* 0^* = (0|1)^*$ (either a string has a longest substring ending in $01$ or not). Hence $R = (0|1) (0|1)^* 0 = S_2$.