Key Answers for Homework #6

1. Using the partition technique find the reduced DFA (i.e., the minimum state DFA that accepts the same language) of the following DFA. For your answer you should also show your partitioning record.

Solution: State reduction by partitioning:

Step 0 (initial partition): partition according to accepting/non-accepting:

P1 P2

----------------- ----------

{1, 2, 4, 5, 6, 8} {3, 7}

Step 1: Analyze the responses for each input symbol:

P1 P2

--------------------------- -----------------

a P1 P2 P2 P1 P2 P2 a P1 P2

{1 2 4 5 6 8 } {3 7}

b P1 P2 P2 P1 P2 P2 b P2 P1

Partition the sets according to the responses:

P11 P12 P21 P22

---------- ------------------- ---- -----

{1 5} {2 4 6 8} {3} {7}

Step 2: Analyze the responses for each input symbol:

P11 P12 P21 P22

--------- ------------------------ ------ ----

a P12 P12 P22 P21 P21 P22

{1 5} {2 4 6 8} {3} {7}

b P12 P12 P21 P22 P22 P21

Partition:

P11 P121 P122 P21 P22

--------- -------- --------- ----- -------

{1 5} (2 8} {4 6} {3} {7}

Step 3: Analyze the responses for each input symbol:

P11 P121 P122 P21 P22

--------- ---------- ----------- ----- -------

a P122 P121 P22 P22 P21 P21

{1 5} {2 8} {4 6} {3} {7}

b P122 P121 P21 P21 P22 P22

Partition: No new partition (procedure ends)

P11 P121 P122 P21 P22

--------- -------- --------- ----- -------

{1 5} (2 8} {4 6} {3} {7}

2. Let L be the language of the following grammar G1. Construct a regular grammar whose language is LR, i.e., the reversed language of L. Your grammar’s production rules should observe the restriction that the nonterminal symbol at the right side of each production rule, if any, should be located at the right end. You should also clearly show the procedure that you took to get your answer.

G1:

S ® aA | bB A ® bD | e B ® aC | bE

C ® aC | bE | e D ® aE | bD | e E ® aE | bD

Solution:

Step 1: Construct FA from G1:

Step 2: Add a new accepting state F:

Step 3: Let the new accepting state be the start state S, reverse the direction of all the edges, and the old start state S be the only accepting state F.

Step 4: Write the grammar from the new Automaton

S®A|D|C A®aF B®bF C®aB|aC

D®bA|bD|bE E®aD|bB|bC|aE F®e

3. Let L be the language of the above grammar G1. Construct a regular grammar whose language is the complement of L. You should also clearly show the procedure that you took to get your answer.

Solution:

Step 1: Construct FA from G1:

Step 2: Add a dead state for undefined transitions. Notice that usually we do not show the dead state just for convenience.

Step 3: Change all the accepting states to non-accepting states and all the no-accepting states to accepting states:

4. Let L’ be the language of grammar G2 below and L be the language of grammar G1 in problem 2 above.

(a) Construct a context-free grammar whose language is L’L, the concatenation of the two languages.

(b) Construct a context-free grammar whose language is L’ È L, the union of the two languages.

G2: S ® aA A ® Sb | b

You should also clearly show the procedure that you took to get your answers.

Solution:

(a) Step 1: First change the nonterminal symbols of G1 and G2 to make them disjoint:

G1: S1 ® aA | bB A ® bD | e B ® aC | bE

C ® aC | bE | e D ® aE | bD | e E ® aE | bD

G2: S2 ® aT T ® S2b | b

Step 2: Construct a regular grammar G with production rules S ® S1S2 and all the rules in G1 and G2:

S®S1S2 S1 ® aA | bB A ® bD | e B ® aC | bE

C ® aC | bE | e D ® aE | bD | e E ® aE | bD

S2 ® aT T ® S2b | b

(b) We simply change S®S1S2 to S®S1 | S2 in the above grammar.

5. Convert the following CFG G to another CFG G’ such that L(G) = L(G’) and G’ has the smallest possible number of e-production rules.

You should also clearly show the procedure that you took to get your answer.

G: S ®ABCd | BEF A ®aA | e B ®FGH | b

C ®cC | e E ® a | e F ® f | e

G ®Gg | H H ®h | e

Solution:

Step 1: Find the set W of all nonterminals of G which derive e as follows;

W0 = {A, C, E, F, H}

W1 = W0Ç{G} = {A, C, E, F, H, G}

W2 = W0Ç{B} = {A, B, C, E, F, H, G}

W3 = W0Ç{S} = {A, C, E, F, H, G, B, S}

W4 = W0Ç{ } = {A, C, E, F, H, G, B, S} = W3

Let W = {A, C, E, F, H, G, B, S}.

Step 2: Delete all e-production from P. Call this new set of productions P1.

S ®ABCd | BEF A ®aA B ®FGH | b

C ®cC E ® a F ® f

G ®Gg | H H ® h

Step 2: Using W = {A, B, C, E, F, H, G, S} modify production rules in P1 to P´ as follows: If a production A ® a is in P1, then put the rules A ® a and A ® b into P´, for all b (¹e ), which are obtained from a by deleting one or more nonterminals in the set W constructed in Step 1 as follows.

S ®ABCd | Abd | Acd | BCd | Ad | Bd | Cd | d | BEF | BE | BF | EF | B | E | F

A ®aA | a

B ®FGH | FG | FH | GH | F | G | H | b

C ®cC | c

E ® a

F ® f

G ®Gg | H | g

H ® h

Step 3 (final result): Since S is in W, we finally add S ® e in P´ and get the following.

S®ABCd | Abd | Acd | BCd | Ad | Bd | Cd | d | BEF | BE | BF | EF | B | E | F | e

A ®aA | a

B ®FGH | FG | FH | GH | F | G | H | b

C ®cC | c

E ® a

F ® f

G ®Gg | H | g

H ® h

The following 2 problems are design applications of finite state automata.

6. Consider a toy shown in Figure 1 below . A sequence of marbles is dropped in, each at gate A or B. Levers x1 and x2 cause the marble to fall either to the left or right. Whenever a marble hit a lever, it causes the lever to change the position so that the next marble to encounter the lever will take the opposite path. The figure shows the initial states of the levers. Model this toy by a DFA. Design your machine such that it enters an accepting state when the last marble comes out of exit D. Denote a marble put in at A by a 0 input, and a marble put in at B by a 1 input.

Solution:

Let \ and / denote the lever positions that open the cannel to the right and left, respectively. (Notice that initially both of the levers are in R.) For Y1, Y2 Î {\, /}, as shown below (see the start state) let Y2Y1 represents current state of the toy, where Y1 and Y2 show, respectively, the positions of levers X1 and X2. There are 8 possible states: 4 accepting states and 4 non-accepting states. But it turns out that only 5 of them can be reached from the starting state \\.

7. Historically, finite state automata were first used to model neuron (nerve cell) nets (see Figure 2 on the following page). Each neuron has excitatory (empty circles in the figure) and inhibitory (filled circles) synapses. A neuron produces a 1-output if the number of excitatory synapses with 1-inputs exceeds the number of inhibitory synapses with 1-inputs by at least the threshold of the neuron (the number inside the triangle). Model the neuron net in Figure 2 in term of a DFA which enters an accepting state if the neuron net’s output is 1. Assume that there is sufficient time for an input signal (either 1 or 0) to propagate and let the network reach a stable configuration before another input comes. Further assume that initially the values in y1, y2, and y3 are all 0.

Solution:

With the output values of the three neurons y1, y2, y3 Î {0, 1} let y1y2y3 represent the state of the net. There are 23 = 8 possible states. But it turns out that only 3 of them can be reached from start state 000 of the machine as shown below.