258 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 | 258 views

Assume , $\sum = {\sigma}$

DFA 'M'

$M = (Q,\Sigma, \delta,q_0,F)$

Let, $Q = \{q_0,q_1\}, F= {q_1}$ and the transition function be defined as -

$\delta:$

$L = \{\sigma,\sigma_3,\sigma_5\ldots \}$ (odd number of $\sigma s$)

NFA $'M_2'$

$M_2 = (Q_2,\sigma,\delta_2,q_{00},F_2)$

$Q_2 = \{q_{00},$

• $\langle q_0,q_0,q_0 \rangle$
• $\langle q_0,q_0,q_1\rangle$
• $\langle q_0,q_1,q_0\rangle$
• $\langle q_0,q_1,q_1\rangle$
• $\langle q_1,q_0,q_0\rangle$
• $\langle q_1,q_0,q_1\rangle$
• $\langle q_1,q_1,q_0\rangle$
• $\langle q_1,q_1,q_1\rangle$}

Now, (A) $F_2 = A = \{\langle p,q,r \rangle\mid p \in F; q,r \in Q\} \forall p,q,r \in Q$ & $\sigma \in \Sigma$

Now NFA $M_2$ will be

$L' = \{\sigma,\sigma_3,\sigma_5\ldots \}$

so $L' = L$ so $M_2 \equiv M$

$\Rightarrow$ we can take other transition rules for 'M' like_

1.  2.   etc or $Q= \{q_0,q_1,q_2\ldots \}$

in all cases, $L' = L$ because, we have to start with triplet $\langle q_0, , \rangle$ & then follow the path as in 'M' and first part of the triplet is important here because it shows the final state of NFA 'M2' since $\Sigma = \{\sigma\}$ only, we have to trace first part of the triplet of $M_2$ which is same as tracing of DFA 'M'

by Boss (16.4k points)
edited
0