Notes - Models of Computation MT23, NFAs

Created: October 11, 2023

Flashcards

Can you give the formal definition of an NFA?

A 5-tuple $(Q, \Sigma, \delta, q _ 0, F)$ where

  • $Q$ is a finite set of states
  • $\Sigma$ is a finite set called the “alphabet”
  • $\delta : Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal P(Q)$ is the transition function
  • $q _ 0 \in Q$ is the initial state
  • $F \subseteq Q$ is the set of accepting states

If we have an NFA $N = (Q, \Sigma, \delta, q _ 0, F)$, then can you formally define the language accepted by $N$?

For $a \in \Sigma \cup \{\epsilon\}$, let $q \to^a q’$ iff $q’ \in \delta(q, a)$. Let $q \Longrightarrow^\epsilon q’$ if $q = q’$ or there exists a sequence of states $q _ 1, \cdots, q _ n$ such that $q _ 1 = q$ and $q _ n = q’$ such that for each $i$, $q _ {i} \to^\epsilon q _ {i+1}$. For $w = a _ 1 \cdots a _ n$ with $a _ i \in \Sigma$, let $q \Longrightarrow^w q’$ iff there are states $q _ 1, q _ 1’, q _ 2, q _ 2’, \cdots, q _ n, q _ n’$ such that

\[q \Longrightarrow^\epsilon q_1 \longrightarrow^{a_1} q_1' \longrightarrow \cdots \longrightarrow q_n \Longrightarrow^\epsilon q_n' \longrightarrow^{a_n} q'\]

Then $w \in \Sigma^\star$ is in the language of $N$ iff $\exists q \in F$ such that $q _ 0 \Longrightarrow^w q$.

What does it mean to say $q \xRightarrow[]{\epsilon} q’$ in the context of finite automata?

There exist $\epsilon$-transitions

\[q \xrightarrow[]{\epsilon} \cdots \xrightarrow[]{\epsilon} q'\]

What does it mean to say $q \xRightarrow[]{w} q’$ where $w = a _ 1 a _ 2 \cdots a _ n \ne \epsilon$?
\[q \xRightarrow[]{\epsilon} q_1 \xrightarrow[]{a_1} q_1' \xRightarrow[]{\epsilon} q_2 \xrightarrow[]{a_1} \cdots \xrightarrow[]{a_n} q_n' \xRightarrow[]{\epsilon} q'\]

What does it mean for an NFA to accept some string?

There is some path through which the string is accepted.

Suppose you have an NFA $N = (Q _ N, \Sigma, \delta _ N, q _ N, F _ N)$ recognising $L$. How can you define a DFA $\mathcal PN$ that recognises $L$?

(The powerset construction)

\[\mathcal P N = (Q_{\mathcal P N}, \Sigma, \delta_{\mathcal P N}, q_{\mathcal P N}, F_{\mathcal P N})\]

where

  • $Q _ {\mathcal P N} = \{ S : S \subseteq Q _ N \} = \mathcal P(Q _ N)$
  • $S \xrightarrow[]{a} S’ \iff S’ = \{q’ : \exists q \in S \text{ s.t. } q \xRightarrow[]{a} q’ \text{ in } N\}$
  • $q _ {\mathcal P N} = \{q : q _ N \xRightarrow[]{\epsilon} q \}$
  • $F _ {\mathcal P N} = \{S \in Q _ {\mathcal P N} : F _ N \cap S \ne \varnothing\}$

Suppose you have two NFAs $N _ 1 = (Q _ 1, \Sigma, \delta _ 1, q _ 1, F _ 1)$ and $N _ 2 = (Q _ 2, \Sigma, \delta _ 2, q _ 2, F _ 2)$ which recognise $A$ and $B$ respectively. How can you define an NFA that recognises both?
\[N = (Q, \Sigma, \delta, q, F)\]

where

  • $Q = (Q _ 1 \times \{1\}) \cup (Q _ 2 \times \{2\}) \cup \{q\}$
  • $F = (F _ 1 \times \{1\}) \cup (F _ 2 \times \{2\})$
  • $\delta(q, \epsilon) = \{(q _ 1, 1), (q _ 2, 2)\}$
  • $\delta((r, 1), a) = \{(r’, 1) : r’ \in \delta _ 1 (r, a)\}$
  • $\delta((r, 2), a) = \{(r’, 2) : r’ \in \delta _ 2 (r, a)\}$

Suppose you have two NFAs $N _ 1 = (Q _ 1, \Sigma, \delta _ 1, q _ 1, F _ 1)$ and $N _ 2 = (Q _ 2, \Sigma, \delta _ 2, q _ 2, F _ 2)$ which recognise $A$ and $B$ respectively. How can you define an NFA that recognises the concatentation $A \cdot B$?
\[N = (Q, \Sigma, \delta, (q_1, 1), F)\]

where

  • $Q = (Q _ 1 \times \{1\}) \cup (Q _ 2 \times \{2\})$
  • $F = (F _ 2 \times \{2\})$
  • $\delta(q, \epsilon) = \{(q _ 1, 1), (q _ 2, 2)\}$
  • $\delta((r, 1), a) = \{(r’, 1) : r’ \in \delta _ 1 (r, a)\}$ if $a \ne \epsilon$ or $r \notin F _ 1$
  • $\delta((r, 1), \epsilon) = \{(r’, 1) : r’ \in \delta _ 1 (r, \epsilon)\} \cup \{(q _ 2, 2)\}$ if $r \in F _ 1$
  • $\delta((r, 2), a) = \{(r’, 2) : r’ \in \delta _ 2 (r, a)\}$

Suppose you have an NFA $N _ 1 = (Q _ 1, \Sigma, \delta _ 1, q _ 1, F _ 1)$ that recognises $L$. How can you define an NFA that recognises $L^\star$?:

\[N = (Q_1 \cup \\{q_0\\}, \Sigma, \delta, q_0, F_1 \cup \\{q_0\\})\]

where

\[\delta(q, a) = \begin{cases} \delta_1(q,a) &\text{if } q \in Q_1 \text{ and } q \notin F_1 \\\\ \delta_1(q, a) &\text{if } q \in F_1 \text{ and } a \ne \epsilon \\\\ \delta_1(q, a) \cup \\{q_1\\} &\text{if } q \in F_1 \text{ and } a = \epsilon \\\\ \\{q_1\\} &\text{if } q = q_0 \text{ and } a = \epsilon \\\\ \varnothing &\text{if } q = q_0 \text{ and } a \ne \epsilon \end{cases}\]

Quickly go over the construction used to show that NFAs are closed under Kleene star.
  • Add a new start state that is accepting, with a $\epsilon$-transition to the actual start state.
  • Add new $\epsilon$-transitions from the accepting states of the original to the original start state (not the new one).

What set of languages are used to show that NFAs can be exponentially more compact than DFAs, and what’s the rough idea behind the proof?
\[L_n = \\{w \mid \text{the }n\text{-th last letter of }w\text{ is }1\\}\]
  • Easy to construct an NFA
  • Can use Myhill-Nerode to show that the size of the smallest DFA recognising $L _ n$ is at least $2^n$.

Quickly prove that NFAs and DFAs can recognise the same languages.

Use the powerset construction and double inclusion.

\[\mathcal P N = (Q_{\mathcal P N}, \Sigma_{\mathcal P N}, \delta_{\mathcal P N}, q_{\mathcal P N}, F_{\mathcal P N})\]

where

  • $Q _ {\mathcal P N} = \{ S : S \subseteq Q _ N \} = \mathcal P(Q _ N)$
  • $\Sigma _ {\mathcal P N} = \Sigma _ N$
  • $S \xrightarrow[]{a} S’ \iff S’ = \{q’ : \exists q \in S \text{ s.t. } q \xrightarrow[]{a} q’ \text{ in } N\}$
  • $q _ {\mathcal P N} = \{q : q _ N \xRightarrow[]{\epsilon} q \}$
  • $F _ {\mathcal P N} = \{S \in Q _ {\mathcal P N} : F _ N \cap S \ne \varnothing\}$


Related posts