MHB Convert an automaton into a regular expression

Thread starter mathmari
Start date Mar 26, 2015
Tags

Convert Expression Regular

AI Thread Summary

To convert an automaton into a regular expression, one must follow a systematic approach that typically involves state elimination or constructing a generalized transition graph. Key steps include identifying the states and transitions of the automaton, systematically removing states while updating transitions to reflect the remaining structure, and ultimately expressing the language in regular expression form. The process can be complex and is well-documented in theory of computation literature. For detailed guidance, refer to the recommended textbooks on the subject. Understanding these steps is crucial for accurately deriving a regular expression from an automaton.

Mar 26, 2015

mathmari

Gold Member

MHB

Hey!

How can we find the regular expression of a language given by an automaton M??

Could you give some hints?? (Wondering)

Which are the steps that we have to follow so that we convert an automaton into a regular expression?? (Wondering)

Physics news on Phys.org

Mar 26, 2015

Evgeny.Makarov

Gold Member

MHB

This is described in the three books on the theory of computation I recommended.

Thread 'Formal derivation of statement from Peano Arithmetic system'

I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...

View full post »