4) (15 marks) Submit answer to this question in a plain-text file named alq4.txt using the submit-nlp command. Clearly separate a) and b) parts in the solution. Consider an NFA (Non-deterministic Finite Automaton) described by the following graph: a,b,n a a) (5 marks) Give three examples of words accepted by this NFA. Briefly describe what language is accepted by this NFA. b) (10 marks) Translate this NFA into a DFA using the process discussed in class. Submit your solution in plain text (as a part of file alq4.txt), where the DFA is shown as the textual table in a format shown below. You must use the process described in class, and follow the required format. State . a . b n | -----------+-----------------+--------+ S: q0q1 | q0q1 | q0q1 | q0q1| ----+----- -- - +-- -- -- -+-- -- -- -+ q0q1 | q0q2 | q0q2 | q0q2 | - --- -- ---- +--- - ---+--------+--------+ F: q0q2 | q0q1 | q0q1 | q0q1 | ------+--------+--------+--------+ Explanation: Use characters minus, vertical line, and plus to draw the table. The columns correspond to input characters. The DFA states are set of NFA states shows as sequences of states in a sorted order by index (for example, use q0q1 rather than q1q0). use labels S: and F: to denote start and finish states. If an NFA state is empty set, then use the word empty' to denote it. 4) (15 marks) Submit answer to this question in a plain-text file named alq4.txt using the submit-nlp command. Clearly separate a) and b) parts in the solution. Consider an NFA (Non-deterministic Finite Automaton) described by the following graph: a,b,n a a) (5 marks) Give three examples of words accepted by this NFA. Briefly describe what language is accepted by this NFA. b) (10 marks) Translate this NFA into a DFA using the process discussed in class. Submit your solution in plain text (as a part of file alq4.txt), where the DFA is shown as the textual table in a format shown below. You must use the process described in class, and follow the required format. State . a . b n | -----------+-----------------+--------+ S: q0q1 | q0q1 | q0q1 | q0q1| ----+----- -- - +-- -- -- -+-- -- -- -+ q0q1 | q0q2 | q0q2 | q0q2 | - --- -- ---- +--- - ---+--------+--------+ F: q0q2 | q0q1 | q0q1 | q0q1 | ------+--------+--------+--------+ Explanation: Use characters minus, vertical line, and plus to draw the table. The columns correspond to input characters. The DFA states are set of NFA states shows as sequences of states in a sorted order by index (for example, use q0q1 rather than q1q0). use labels S: and F: to denote start and finish states. If an NFA state is empty set, then use the word empty' to denote it
