# Convert a non-deterministic finite automata to a regular expression.

• MHB
• JamesBwoii
In summary, the conversation is about converting an NFA to a regular expression. The person has come up with an answer but is unsure if it is correct. They provide a link to the question and their workings. Another person points out an error in the workings and asks for the source of the conversion procedure. The person clarifies the mistake in their workings and explains the conversion procedure taught in their lectures. They also post a photo of their lecture notes. The conversation ends with the person stating that they have managed to solve the problem.
JamesBwoii
Hi, and welcome to the forum!

In the first image, you have an arrow labeled just be $b$ from the second state to the accepting state, but in the first automata in the second image, this arrow is labeled by $a,b$.

Also, which book or source describes the conversion procedure you are using?

Sorry, the first image is the correct one and the one I have drawn at the top of the page is a mistake.

As for the procedure it is a method that has been taught to us in lectures, although I could be misunderstanding it, here is how I take it:

Firstly, the NFA must be preprocessed such that:
1. Has a single final state.
2. Initial state does not have any incoming arrows.
3. Final state has no out going arrows.

As for the conversion algorithm, I will post a photo of my lecture notes as I feel that will represent it best - http://i.imgur.com/kbbVD1w.png

EDIT: I've managed to solve it now.

Last edited:

## What is a non-deterministic finite automaton (NFA)?

A non-deterministic finite automaton is a mathematical model used to recognize patterns in strings of symbols. It is composed of a finite number of states and transitions between these states based on input symbols.

## Why would I want to convert an NFA to a regular expression?

Converting an NFA to a regular expression allows for a simpler and more efficient representation of the language recognized by the automaton. Regular expressions are also commonly used in programming languages and software applications for pattern matching.

## What is the process for converting an NFA to a regular expression?

The process involves using the state elimination method, which involves systematically eliminating one state at a time from the NFA and replacing it with a regular expression until only one state remains. This final regular expression represents the language recognized by the original NFA.

## Is converting an NFA to a regular expression always possible?

Yes, it is always possible to convert an NFA to a regular expression. However, the resulting regular expression may not necessarily be the most simplified or efficient representation of the language recognized by the NFA.

## What are some common tips for converting an NFA to a regular expression?

Some tips include thoroughly understanding the state elimination method, using a table to keep track of the regular expressions for each state, and simplifying the resulting regular expression by applying algebraic laws for regular expressions.

• Set Theory, Logic, Probability, Statistics
Replies
2
Views
13K
• Programming and Computer Science
Replies
6
Views
3K
• Programming and Computer Science
Replies
2
Views
2K
• Atomic and Condensed Matter
Replies
4
Views
2K
• Chemistry
Replies
16
Views
3K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Introductory Physics Homework Help
Replies
3
Views
4K
• Quantum Interpretations and Foundations
Replies
138
Views
6K
• Special and General Relativity
Replies
40
Views
2K
• General Math
Replies
5
Views
4K