GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
74 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\}$

asked in Theory of Computation by Veteran (79.1k points)  
edited by | 74 views

Please log in or register to answer this question.



Top Users Aug 2017
  1. ABKUNDAN

    4660 Points

  2. Bikram

    4366 Points

  3. akash.dinkar12

    3258 Points

  4. rahul sharma 5

    3042 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2410 Points

  7. just_bhavana

    2100 Points

  8. Tesla!

    1918 Points

  9. stblue

    1682 Points

  10. joshi_nitish

    1608 Points


24,928 questions
32,024 answers
74,385 comments
30,113 users