Definition Non Deterministic Finite Automata

A non-deterministic finite automaton (NDFA/NFA) is a 5-tuple (Q, Σ, δ, q0, F) 


Q = is a finite set of states. 

Σ = is a finite set of input symbols. 

δ = is a transition function mapping from Q × Σ to 2Q

q0 = is the initial state, q0 ∈ Q. 

F = is a set of final states, F ⊆ Q.

For example,

Consider the NFA that accepts all string ending with 01.

Transition diagram
Transition table

In this NFA, 

M = {Q, Σ, δ, q0, F} 


Q = {q0, q1, q2}. 

Σ = {0, 1}. 

δ = As shown above. 

q0 = Initial state. 

F = {q2}

Some terms in NFA:

Alphabet: An alphabet is a finite, non-empty set of symbols. 

Generally “Σ” is used to devote the alphabet. 

For example,

Σ = {0, 1} 

Σ = {a, b}

Symbol: Any character, number or special symbol can be treated as a “symbol”. It is the member of the alphabet.

For example,

In above alphabet 0, 1 is symbol.

Word: A word or string is a finite sequence of symbols. 

For example,

S = 0110

S = ababa. 

Q1: What is an NFA?

Ans: An NFA (Nondeterministic Finite Automaton) is a type of automaton used in computer science and mathematics to recognize regular languages. It is a theoretical model of computation that consists of a set of states, a set of input symbols, a transition function, an initial state, and a set of final states.

Q2: How is an NFA different from a DFA?

Ans: An NFA is different from a DFA (Deterministic Finite Automaton) in that it allows for multiple possible transitions from a given state on a given input symbol. In other words, an NFA can be in multiple states at once and can have multiple possible next states for a given input symbol. A DFA, on the other hand, must have a unique next state for each input symbol and each state.

Q3: How is the transition function defined in an NFA?

Ans: The transition function in an NFA maps a state and an input symbol to a set of possible next states. Formally, the transition function can be defined as: δ: Q × Σ → P(Q), where Q is the set of states, Σ is the input alphabet, and P(Q) is the power set of Q.

Q4: How is the language recognized by an NFA defined?

Ans: The language recognized by an NFA is defined as the set of all input strings that cause the NFA to end up in a final state. Formally, L(N) = {w | δ(q0, w) ∩ F ≠ ∅}, where N is the NFA, q0 is the initial state, w is an input string, δ is the transition function, and F is the set of final states.

EasyExamNotes © 2023