Question

Please answer c,d,f. also please explain the answers for me to understand.

For each of the languages below, draw the state diagram for a nondeterministic finite automaton (NFA) to accept the language. In order to get full marks, your NFA must have the number of states specified, and it must take advantage of nondeterminism. [There must be at least one case where the machine has a choice between two or more next states on some input symbol, or a case where the machine has no possible next state on a particular input symbol, or you must use Q-transitions in a non-trivial way).] (c) (8 marks) L3 = {W € {0, 1, 2}* | w contains both the substring 01 and the substring 21}; use no more than 11 states. (d) (8 marks) L4 = {W € {a,b,c} | w starts with ab or ends with ab}; use no more than 7 states. (Note: The or above is an inclusive-or. For example, the string abcbab is in L4.) (f) (8 marks) L6 = {w E {0,1}* | || is odd and w contains at least one occurrence of the substring 10}; use no more than 13 states. (1 bonus mark for a correct solution that uses no more than 6 states

Answer 1

20. ----- -- 9600 2012

IN HORIZONTAL : FIRST HAVING 01 AND 21

TO ACCEPT A STRING IT SHOULD CONTAIN BOTH 01 AND 21 AS SUB-STRINGS .

SO ANYTHING IN THE STRING BEFORE 01 IS STILL IN THE STATE q0 AND WHEN IT COMES 01 IT REACHES q2

STATE .

AND ANYTHING OTHER THAN 21 IT STILL STAYS IN THE STATE q2 BUT IF IT 21 THEN IT GOES TO THE FINAL STATE . IE,. q4 . BECAUSE IT HAVE BOTH THE SUB-STRINGS 01 AND 21 , SO THE STRING IS FINALLY ACCEPTED BY THE NFA .

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

IN VERTICAL : FIRST HAVING 21 AND 01

TO ACCEPT A STRING IT SHOULD CONTAIN BOTH 01 AND 21 AS SUB-STRINGS .

SO ANYTHING IN THE STRING BEFORE 21 IS STILL IN THE STATE q0 AND WHEN IT COMES 21 IT REACHES q6

STATE .

AND ANYTHING OTHER THAN 01 IT STILL STAYS IN THE STATE q6 BUT IF IT 01 THEN IT GOES TO THE FINAL STATE . IE,. q8 . BECAUSE IT HAVE BOTH THE SUB-STRINGS 01 AND 21 , SO THE STRING IS FINALLY ACCEPTED BY THE NFA .

AFTER HAVING THE BOTH SUB-STRINGS 01 AND 21 ANY-SEQUENCE OF 0,1,2 IS ACCEPTED .

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

(d) (4={WE {a,b,c}* I w starts with ab or ends with ab} NFA FOR 14: an apabic Ya, bic (23 Dabic

IN HORIZONTAL : q0 , q1 , q3

WHEN THE STRING STARTS WITH ab THEN IT REACHES TO THE FINAL STATE q2.

IN VERTICAL : q0,q3,q4q5

WHEN THE STRING HAVING ANY NUMBER OF CHARACTERS IN ANY ORDER STILL STAYS IN STATE q3 AND THE STRING IS ENDED WITH ab , THEN IT GOES INTO THE FINAL STATE q5.

HERE WE ARE CONSTRUCTING NFA , SO THE STRING IS ACCEPTED BY THE NFA AS IT REACHES THE ANY ONE OF THE FINAL STATE IN ANY-ORDER OF POSSIBLE ORDERS.

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

(f) (6=60620,12* | iwl is ode and a contains at least one occurrence of the substring 10%

EXPLANATION :

TO ACCEPT A STRING IT SHOULD CONTAIN THE SUB-STRING 10 AT-LEAST ONCE SO WE TO REACH THE FINAL STATE IN THE NFA ,IE ,. q5 IN THE PATH IT SHOULD CONTAIN THE SUB-STRING 10 AND IT ALSO HAVE THE ODD LENGTH .

SO BY THE ABOVE NFA ALL THE STRINGS HAVING ODD LENGTH AND HAVING SUB-STRING 10 IS ACCEPTED .