COMPILER DESIGN

Detailed explanation-1: -Let language L ⊆ *, and suppose L is accepted by NFA N = (, Q, q0, F, ). There exists a DFA D= (, Q’, q’0, F’, ’) that also accepts L. (L(N) = L(D)). By allowing each state in the DFA D to represent a set of states in the NFA N, we are able to prove through induction that D is equivalent to N.

Detailed explanation-2: -What is the relation between NFA-accepted languages and DFA accepted languages? Explanation: The no of languages accepted by NFA and DFA is equal.

Detailed explanation-3: -Every DFA has an equivalent NFA. (Proof by construction-trivial.) Given N = (Q, , , q0, F), and NFA recognizing some language A. We prove that every NFA has an equivalent DFA by showing how to construct a DFA N from N that recognizes the same language A.

Detailed explanation-4: -DFA has only one move on a given input symbol. Let, M = (Q, ∑, , q0, F) is an NFA which accepts the language L(M). There should be equivalent DFA denoted by M’ = (Q’, ∑’, q0’, ’, F’) such that L(M) = L(M’).

Detailed explanation-5: -The languages that can be recognized by an NFA are known as regular languages. In an NFA, the automaton can be in multiple states simultaneously, and it may have multiple transitions from a single state on the same input symbol.