Computer science(Theory of Computation)

Exercise 1:

1- Write the formal definition of a finite state machine

Exercise 2:

Consider the NFA defined as:

N=({q0,q1,q2},{a,b}, , q0,{q1}) defined by

Draw the corresponding automaton using JFLAP.

Find 3 strings accepted by the automaton and 3 string rejected by the automaton.

What is q2?

What language does this automaton accept?

Exercise 3:

Consider the DFA below

-Write its formal definition

-Which of the strings 0001,01001,0000110 are accepted by the DFA

Exercise 4:

For ={a,b}, construct using JFLAP DFA’s that accept the sets of strings consisting of

a- all strings with exactly one a, (test yes: a, bbabb, abbb, bba. Test no: aa, aba, bbbaa)

b- all strings with no more than 3 a’s (strings with 1, 2 or 3 a’s should be accepted) (test yes: a, bbabab, abbaab, bba. Test no: aaaa, abaaa, aabbbaa)

c- all strings with at least one a and exactly 2 b’s (Yes: abb, bbaaaa, babaaaa, no: bb, bbabbb, abbb, bbabb)

d- Language L ={ab3wb2 : w {a,b}*}(yes: abbbaaabb, abbbbababb, abbbaaaababb, no: bbbab, abbaabbabb}