The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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

  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)$


$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 (99.8k points)
edited by | 145 views


Please log in or register to answer this question.

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

38,115 questions
45,622 answers
49,306 users