Convert an NFA to a DFA (Subset Construction) and Describe the Accepted Language

We will determinize the given $\epsilon$-free NFA using Powerset/Subset Construction. After building the DFA transition table, we will Accepting State (DFA) characterization to informally describe the language.

We are given NFA states $\{p,q,r,s,t\}$ with start state $p$ and accept state $s$. Transitions (from the table):

• From $p$: on input $0$, go to $\{p,q\}$; on input $1$, go to $\{p\}$.
• From $q$: on input $0$, go to $\{r,s\}$; on input $1$, go to $\{t\}$.
• From $r$: on input $0$, go to $\{p,r\}$; on input $1$, go to $\{t\}$.
• From $s$: on both $0$ and $1$, go to $\emptyset$.
• From $t$: on both $0$ and $1$, go to $\emptyset$.

Key terms we will use:

• DFA
• NFA
• Transition Function
• Language
• Accepting State

A compact way to keep track is the DFA transition rule: If the current DFA state is a set $S$ of NFA states, then on symbol $a\in\{0,1\}$ the next DFA state is

$$\delta_{\text{DFA}}(S,a)=\bigcup_{x\in S}\delta_{\text{NFA}}(x,a).$$

This is the core of Subset Construction.

1) Enumerate DFA states (subsets) reachable from the start

Start subset: $A_0=\{p\}$.

Now compute systematically.

From $\\{p\\}$

• On $0$: $\delta(p,0)=\{p,q\}$, so $\{p\}\xrightarrow{0}\{p,q\}$.
• On $1$: $\delta(p,1)=\{p\}$, so $\{p\}\xrightarrow{1}\{p\}$.

So we discover $A_1=\{p,q\}$.

From $\\{p,q\\}$

• On $0$:
  • from $p$ on $0$ gives $\{p,q\}$
  • from $q$ on $0$ gives $\{r,s\}$
  • union: $\{p,q\}\cup\{r,s\}=\{p,q,r,s\}$ Hence $\{p,q\}\xrightarrow{0}\{p,q,r,s\}$.
• On $1$:
  • from $p$ on $1$ gives $\{p\}$
  • from $q$ on $1$ gives $\{t\}$
  • union: $\{p,t\}$ Hence $\{p,q\}\xrightarrow{1}\{p,t\}$.

So we discover $A_2=\{p,q,r,s\}$ and $A_3=\{p,t\}$.

From $\\{p,t\\}$

• On $0$: $p \xrightarrow{0}\{p,q\}$ and $t\xrightarrow{0}\emptyset$, union $\Rightarrow \{p,q\}$.
• On $1$: $p \xrightarrow{1}\{p\}$ and $t\xrightarrow{1}\emptyset$, union $\Rightarrow \{p\}$.

So $A_3 \xrightarrow{0} A_1$ and $A_3 \xrightarrow{1} A_0$.

From $\\{p,q,r,s\\}$

• On $0$:
  • $p \xrightarrow{0} \{p,q\}$
  • $q \xrightarrow{0} \{r,s\}$
  • $r \xrightarrow{0} \{p,r\}$
  • $s \xrightarrow{0} \emptyset$ union: $\{p,q\}\cup\{r,s\}\cup\{p,r\}\cup\emptyset=\{p,q,r,s\}$ Hence it loops: $\{p,q,r,s\}\xrightarrow{0}\{p,q,r,s\}$.
• On $1$:
  • $p \xrightarrow{1} \{p\}$
  • $q \xrightarrow{1} \{t\}$
  • $r \xrightarrow{1} \{t\}$
  • $s \xrightarrow{1} \emptyset$ union: $\{p\}\cup\{t\}=\{p,t\}$ Hence $\{p,q,r,s\}\xrightarrow{1}\{p,t\}$.

So far, we have subsets:
$A_0=\{p\}$, $A_1=\{p,q\}$, $A_2=\{p,q,r,s\}$, $A_3=\{p,t\}$.

Transitions that produce $\\emptyset$

We still should include $\\emptyset$ if any transition ever yields it. Note:

• From any subset we computed, the union always included at least one non-empty target set, so $\\emptyset$ is not reachable from the start under these transitions.
• Still, for completeness, we can define it as a dead DFA state in the construction.

Accepting DFA states

Since $s$ is accepting in the NFA, any DFA subset containing $s$ is accepting. Only $A_2=\{p,q,r,s\}$ contains $s$. So the DFA accepting state set is: $\{A_2\}$.

2) Final DFA transition table

Let the DFA states be:

• $A_0=\{p\}$
• $A_1=\{p,q\}$
• $A_2=\{p,q,r,s\}$
• $A_3=\{p,t\}$
• (optional) $A_4=\emptyset$ (dead)

This DFA is equivalent to the given NFA with respect to the accepted Language.

3) Informal description of the accepted language

Recall: the NFA accepts a string iff at the end there is at least one computation path that places the automaton in state $s$.

From the transition structure:

• The only way to reach $s$ is from $q$ on input $0$: $q \xrightarrow{0} \{r,s\}$.
• Therefore, acceptance requires that at some point (sometime before the end), the NFA simulation can be in state $q$, and the next symbol must be $0$ (so that one branch moves into $s$).
• Once $s$ is reached, it must survive until the end of the input. But from $s$, on both $0$ and $1$, the NFA transitions go to $\emptyset$. That means if you ever consume any further input after first entering $s$, that computation branch dies.
• Hence, for the string to be accepted, you must enter $s$ exactly at the final symbol consumption (i.e., the last symbol must be a $0$ that is taken on a transition out of $q$).

Now observe how $q$ appears:

• $p \xrightarrow{0} \{p,q\}$ introduces $q$ when the machine reads a $0$ while a $p$-branch exists.
• In this NFA, there is always a $p$-branch available at many times (e.g., $p$ loops on input $1$, and also remains available via $0$ transitions from $p$ and $r$).

A simple informal characterization consistent with the DFA:

• The DFA reaches the accepting subset $A_2=\{p,q,r,s\}$ only after reading a prefix that ends with a $0$ while the machine still has an active $q$-branch.
• From the accepting subset, reading another symbol drops you back to non-accepting subsets because $s$ cannot persist (it goes to $\emptyset$ after consuming any further input).

Informal language statement:

The language consists of those binary strings whose last symbol is a $0$, such that just before that last $0$ there is a reachable configuration containing state $q$ (equivalently, the subset construction reaches $\\{p,q,r,s\\}$ exactly after consuming the final symbol).

In terms of the DFA we built:

• You accept exactly when the DFA ends in $A_2$.
• Since $A_2$ transitions on $0$ stay in $A_2$, and on $1$ move to $A_3$, acceptance depends on whether the input ends in a position where $s$ is created by a $q$-$0$ move and no further symbols are read.