+1 vote
55 views

Consider the DFA $M$ and NFA M2  as defined below. Let the language accepted by machine $M$ be $L$. What language machine M2 accepts, if

1. $F2=A$ ?
2. $F2=B$ ?
3. $F2=C$ ?
4. $F2=D$ ?
• $M=(Q, \Sigma, \delta, q_0, F)$
• $M2=(Q2, \Sigma, \delta_2, q_{00}, F2)$

where

$Q2=(Q \times Q \times Q) \cup \{ q_{00} \}$

$\delta_2 (q_{00}, \epsilon) = \{ \langle q_0, q, q \rangle \mid q \in Q\}$

$\delta_2 ( \langle p, q, r \rangle, \sigma ) = \langle \delta (p, \sigma), \delta (q, \sigma), r \rangle$

for all $p, q, r \in Q$ and $\sigma \: \in \: \Sigma$

$A=\{ \langle p, q, r \rangle \mid p \in F; q, r \in Q \}$

$B=\{\langle p, q, r \rangle \mid q \in F; p, r \in Q\}$

$C=\{\langle p, q, r \rangle \mid p, q, r \in Q; \exists s \in \Sigma^* ( \delta (p,s) \in F) \}$

$D=\{\langle p, q, r \rangle \mid p \in Q; q \in F\}$

edited | 55 views