Help with answering the question at the bottom.

Example of Reading an NFA

Q = {q0, q1, q2, q3, q4} F = {q2, q4}

L(M) = {x | x is a binary number that has 2 consecutive 0's or 2 consecutive 1's}

= (0|1)^* (00|11) (0|1)^*

Trs(q0, 0) = {q0, q3} (q0)--0(q3) also, loop on q0 on 0,1

Trs(q0, 1) = {q0, q1} --1(q1)

Trs(q1, 1) = {q2} (q1)--1((q2))

Trs(q2, 0/1) = {q2} loop on q2 on 0,1

Trs(q3, 0} = {q4} (q3)--0((q4))

Trs(q4, 0/1) = {q4} loop on q4 on 0,1

Does this FA work?

• q0 to q4 is possible iff you read 2 0's
• q0 to q2 is possible iff you read 2 1's
• In q0, q4 and q2 you can read any substring and stay there

(denoted by the loops)

If any path ends in q2 or q4, the string is accepted.

Trs*(q0, 010) = {q0, q3} q0 for staying in q0, or

q3 for going there on last 0

Since q0 and q3 are not in F, 010 is not accepted.

Trs*(q0, 01001) = {q0, q1, q4} stay in q0,

or q0 to q1 on last 1,

or q0 to q3 then q4 on 00

Since q4 is in F, 01001 is accepted.

Cannot be a Trs* from this file or other forum answers:

Q. Using the directly above example NFA, give an example Trs*(q0, _______) = { }

to show multiple states you could end up on feeding a string.