T Naughton, NUIM
Back to CS355 home

Lab sheet 4 - Nondeterministic finite automata

In this lab, you will work with nondeterministic finite automata. You don't need your PCs so switch off your monitors. Once again, you will be formed into teams of two persons. The teams will be chosen randomly. This lab will be graded by picking a question typical of the hardest problems on this sheet. For all problems in this lab you can assume that = {0, 1}.

Machine 4.1 Construct a nondeterministic finite automaton (NFA) with three states that accepts the language {w : w ends with 10}. (This means your NFA cannot have more than three states.)

Machine 4.2 Construct a nondeterministic finite automaton (NFA) with five states that accepts the language {w : w contains 1100 as a substring}.

Machine 4.3 Construct a nondeterministic finite automaton (NFA) with six states that accepts the language {w : w contains an even number of 1s, or it contains exactly two 0s}.

Machine 4.4 Construct a nondeterministic finite automaton (NFA) with two states that accepts the language {1}.

Machine 4.5 Construct a nondeterministic finite automaton (NFA) with three states that accepts the language 1*0*1*1.

Machine 4.6 Construct a nondeterministic finite automaton (NFA) with one state that accepts the language {w : w = e}.

Machine 4.7 Construct a nondeterministic finite automaton (NFA) with one states that accepts the language 1*.

Machine 4.8 In lectures you were shown a sequence of steps that can be used to prove that every NFA has an equivalent FA. Use this sequence of steps to construct an equivalent FA for the following NFA. (Do not remove the states that will never be entered. Do not simply figure out the language and write the FA from scratch.)

Machine 4.9 Use the same sequence of steps to construct an equivalent FA for the following NFA. (Do not remove the states that will never be entered. Do not simply figure out the language and write the FA from scratch.)