edited by
8,350 views
40 votes
40 votes

Given below are the transition diagrams for two finite state machines $M_1$ and $M_2$ recognizing languages $L_1$ and $L_2$ respectively.

  1. Display the transition diagram for a machine that recognizes $L_1.L_2$, obtained from transition diagrams for $M_1$ and $M_2$ by adding only $\varepsilon$ transitions and no new states.

  2. Modify the transition diagram obtained in part (a) obtain a transition diagram for a machine that recognizes $(L_1.L_2)^*$ by adding only $\varepsilon$ transitions and no new states.

    (Final states are enclosed in double circles).

edited by

1 Answer

Best answer
42 votes
42 votes

We can combine the final state of $M_1$ with the start state of $M_2$ as follows recognizing $L_1L_2$. But before we combine $M_1$ and $M_2$ remove the final state of $M_1$ as the new machine can accept $L_1$ also while it should accept only $L_1.L2$.

~Pic by Praveeen Saini

edited by

Related questions

40 votes
40 votes
5 answers
1
Kathleen asked Oct 9, 2014
12,797 views
Consider the following state table for a sequential machine. The number of states in the minimized machine will be$$\begin{array}{|l|l|ll|}\hline \text{} & \text{} & \tex...
17 votes
17 votes
2 answers
2
Kathleen asked Oct 9, 2014
5,542 views
Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ be a pushdown automaton accepting by empty stack for the...
6 votes
6 votes
1 answer
3
go_editor asked Feb 10, 2018
2,341 views
Consider the synchronous sequential circuit in the below figureGiven that the initial state of the circuit is $S_4,$ identify the set of states, which are not reachable.
18 votes
18 votes
2 answers
4
Kathleen asked Oct 9, 2014
6,379 views
Consider the synchronous sequential circuit in the below figureDraw a state diagram, which is implemented by the circuit. Use the following names for the states correspon...