The Gateway to Computer Science Excellence
+3 votes
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\}$

in Theory of Computation by Veteran (105k points)
edited by | 258 views

1 Answer

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'

by Boss (16.4k points)
edited by
0
What about B,C,D?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,563 answers
195,735 comments
101,660 users