The Gateway to Computer Science Excellence

+3 votes

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

- $F2=A$ ?
- $F2=B$ ?
- $F2=C$ ?
- $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\}$

0 votes

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'

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,563 answers

195,735 comments

101,660 users