Question

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:

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

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

Try using 1001, does that work?

Answer 1

IF YOU HAVE ANY DOUBTS COMMENT BELOW I WILL BE THERE TO HELP YOU

ANSWER:

EXPLANATION:

as per the quesstion given i am giving this

Yes this FA works as the final states are reachable only if two 0's(q4) or two 1's(q2) have encountered. There my be multiple paths and multiple states we can end into but q2/q4 reachable only if above conditions are met and all the paths to q2 are from q0 & q1 and all the paths to q4 are from q0 & q3, no intersections.

Trs*(q0, 00011) = {q0, q1, q2, q4} shows multiple states you could end up on feeding a string.

hope it helps you

rate thumbsup please