Lab 4 - 09/4 Friday + Quiz 2


Since this is a quiz day, this will be a shorter lab. After your quiz, get some more practice internalizing DFAs, regular expressions and NFAs.

Deconstruction

  1. What language does this DFA accept?

Automaton start start q1 q₁ start->q1 q1->q1 0 q2 q₂ q1->q2 1 q2->q1 1 q3 q₃ q2->q3 0 q3->q3 0 q4 q₄ q3->q4 1 q4->q4 0,1

It suffices to provide a regular expression if an english description is too difficult.

Recognition

  1. What language does the following regular expression represent? \[ (\epsilon+ 1)(01)^{∗}(\epsilon+ 0) \]

Non-deterministic Finite Automata (NFA)

Recall the formal definition of an NFA: an NF A is a 5-tuple \(\left(Q, \Sigma, \delta,q_0, F\right)\) where:

  • \(Q\) is a finite set of states
  • \(\Sigma\) is a finite set of symbols called the alphabet
  • \(\delta\) is the transition function, which maps \(Q \times \Sigma \cup \{\epsilon\}\) to the power set of \(Q\)
  • \(q_0 \in Q\) is the start state
  • \(F \subseteq Q\) is the set of accept states
  1. Formally describe the NFA depicted below. Include the 5-tuple definition, and a transition table.
    1. Does this NFA accept the string 010?
    2. Does this NFA accept the string 010110?

Automaton start q1 q 1 start->q1 q1->q1 0,1 q2 q 2 q1->q2 1 q3 q 3 q2->q3 0, ε q4 q 4 q3->q4 1 q4->q4 0,1

  1. Let \(\Sigma =\) {0,1}. Can you construct a NFA that describes a language:

    \[ L_1 = \left\{ w \in \Sigma^{*} \mid w \textrm{ contains the subsequence } 001 \right\} \]

  2. Let \[ L_2 = \left\{ w \in \{0,1\}^{*} \mid w \textrm{ starts and ends with 0} \right\} \]

    Construct an NFA for \(L_2\) with exactly three states.