NFA Examples with Solutions - Lead Grow Develop - Business, Technology, Personal Development

Learning NFA (Non-deterministic Finite Automata) becomes much easier by solving examples. In this article, you will find multiple NFA examples with solutions, including state diagrams, transition tables, and explanations. These examples are useful for Theory of Computation (TOC) students preparing for university exams and competitive tests.

What is an NFA?

A Non-deterministic Finite Automaton (NFA) is a finite automaton in which a state may have zero, one, or multiple transitions for the same input symbol. An input string is accepted if at least one path leads to a final state.

Characteristics of an NFA

A state can have multiple transitions for the same input.
ε (epsilon) transitions may be allowed in some NFAs.
Multiple computation paths are possible.
Every NFA has an equivalent DFA.

Example 1: NFA Accepting Strings Ending with 01

Problem

Design an NFA that accepts all binary strings ending with 01.

Solution

States: {q0, q1, q2}

Alphabet: {0,1}

Start State: q0

Final State: q2

Transition Table

State	0	1
→q0	{q0, q1}	{q0}
q1	∅	{q2}
*q2	∅	∅

Explanation

q0 keeps reading any binary string.
Whenever a 0 is read, the automaton may move to q1.
If the next symbol is 1, it reaches q2.
Therefore, the string must end with 01.

Accepted Strings

01
101
1101
1001

Rejected Strings

Example 2: NFA Accepting Strings Containing the Substring 11

Problem

Construct an NFA that accepts all binary strings containing the substring 11.

Solution

States: {q0, q1, q2}

Start State: q0

Final State: q2

Transition Table

State	0	1
→q0	{q0}	{q0, q1}
q1	∅	{q2}
*q2	{q2}	{q2}

Explanation

q0 reads any input.
On reading the first 1, it may move to q1.
Reading another 1 moves to q2.
Once q2 is reached, all remaining symbols are accepted.

Accepted Strings

11
110
0110
1110

Rejected Strings

10
101
1000

Example 3: NFA Accepting Strings Beginning with 1

Problem

Design an NFA that accepts all binary strings starting with 1.

Solution

States: {q0, q1}

Start State: q0

Final State: q1

Transition Table

State	0	1
→q0	∅	{q1}
*q1	{q1}	{q1}

Explanation

The first input symbol must be 1.
After reaching q1, any sequence of 0s and 1s is accepted.

Accepted Strings

1
10
111
101010

Rejected Strings

Example 4: NFA Accepting Strings Ending with 10

Problem

Construct an NFA that accepts all strings ending with 10.

Solution

Transition Table

State	0	1
→q0	{q0}	{q0, q1}
q1	{q2}	∅
*q2	∅	∅

Explanation

q0 processes any binary string.
On reading 1, it may move to q1.
Reading 0 after q1 reaches the final state q2.
Thus, only strings ending with 10 are accepted.

Accepted Strings

10
110
1010
0010

Example 5: NFA Accepting Strings with an Even Number of 1’s

Problem

Design an NFA that accepts binary strings containing an even number of 1’s.

Solution

Transition Table

State	0	1
→*q0	{q0}	{q1}
q1	{q1}	{q0}

Explanation

q0 represents an even number of 1’s.
q1 represents an odd number of 1’s.
Every occurrence of 1 changes the parity.

Accepted Strings

ε
11
1010
1100

Rejected Strings

Practice Questions

Try solving the following NFA problems yourself.

Design an NFA that accepts strings ending with 11.
Construct an NFA for strings containing the substring 101.
Design an NFA that accepts strings beginning with 01.
Construct an NFA accepting strings having at least one 0.
Design an NFA accepting strings containing exactly two 1’s.

Tips for Solving NFA Problems

Identify the required language carefully.
Decide the start and final states.
Use multiple transitions when needed.
Verify the automaton using accepted and rejected strings.
Draw the transition table before converting the NFA into a DFA.

Frequently Asked Questions (FAQs)

What is an NFA?

An NFA (Non-deterministic Finite Automaton) is a finite automaton in which multiple transitions for the same input symbol are allowed.

How is an NFA different from a DFA?

An NFA may have multiple possible next states for the same input, whereas a DFA has exactly one transition for each input symbol from every state.

Can every NFA be converted into a DFA?

Yes. Every NFA has an equivalent DFA using the subset construction method.

Why are NFA solved examples important?

Solved examples help students understand state transitions, language acceptance, and automata design techniques used in Theory of Computation.

Conclusion

Practicing NFA examples with solutions is one of the best ways to understand Non-deterministic Finite Automata. By solving different language recognition problems such as strings ending with specific patterns, containing substrings, or satisfying parity conditions, you can build a strong foundation in Theory of Computation and confidently solve NFA design and NFA-to-DFA conversion questions in exams.