Question

(D is a deterministic finite automata (DFA))....{<D,R>} : D is a DFA and R is a regex. Prove that languages is decidable.

(N is an non deterministic finite automata (NFA))...{<N1,N2>}:N1 and N2 are NFAs. Prove that languages is decidable.

Answer 1

(D is a deterministic finite automata (DFA))....{<D,R>} : D is a DFA and R is a regex. Prove that languages is decidable.

Ans: Define the language as

C = {<D, R> | D is a DFA and R is a regular expression with L(D) = L(R) }.

Recall that the proof of Theorem that defines a Turing machine F that decides the language EQDFA = { <A, B> | A and B are DFAs and L(A) = L(B) }. Then the following Turing machine T decides C:

T = “On input <D, R>, where D is a DFA and R is a regular expression:

1. Convert R into a DFA D_R using the algorithm in the proof of Kleene’s Theorem.

2. Run TD decider F from Theorem on input <M, D_R>.

3. If F accepts, accept. If F rejects, reject.”

N is an non deterministic finite automata (NFA))...{<N1,N2>}:N1 and N2 are NFAs. Prove that languages is decidable.

Ans:Nondeterministic finite automata (NFAs) allow for several or no choices to exist for the next state on a given symbol.

• For a state q and symbol l ∈ Σ, NFA can have

1. multiple edges leaving q labelled with the same symbol l
2. no edge leaving q labelled with symbol l
3. edges leaving q labelled with ε

• can take ε-edge without reading any symbol from input string.

Example: NFA N1 with alphabet Σ = {0, 1}.

• Suppose NFA is in a state with multiple ways to proceed, e.g., in state q1 and the next symbol in input string is 1.
• The machine splits into multiple copies of itself (threads).

1. Each copy proceeds with computation independently of others.
2. NFA may be in a set of states, instead of a single state.
3. NFA follows all possible computation paths in parallel.
4. If a copy is in a state and next input symbol doesn’t appear on any outgoing edge from the state, then the copy dies or crashes.

• If any copy ends in an accept state after reading entire input string, the NFA accepts the string.
• If no copy ends in an accept state after reading entire input string, then NFA does not accept (rejects) the string.