2

Let's assume that we have a fsa as follows:

fsa = {0:{'a': 1, else: 2},1:{'b': 1, else: 2},2:{else: 2}}

This means: at state 0, if input is 'a', it goes to state 1, otherwise it goes to state 2; at state 1, if input is 'b', it goes to state 1, otherwise it goes to state 2; at state 2, for any input, it goes to state 2.

Assume, state 0 is a starting state, state 1 is an accepting state and state 2 is the failure state. Then this fsa can be translated as regex "ab*". In fact, there are a few algorithms that translate fsa to regex, such as Brzozowski algebraic method.

My question: can any fsa defined in the above form be translated into a regex? Is there any limitation?

Mark Jin
  • 2,616
  • 3
  • 25
  • 37
  • By definition, regular languages are those whose expressive power are equal to some finite state automaton's. (and vice versa) – a p Aug 03 '15 at 02:35
  • One method to convert from DFA to regex: http://stackoverflow.com/questions/13676431/regular-expressions-with-repeated-characters/13677120#13677120 (Brzozowski Algebraic Method) – nhahtdh Aug 03 '15 at 02:59

4 Answers4

2

Yes, they are mathematically equivalent. 'The equivalence of regular expressions and finite automata is known as Kleene's theorem.'

1983
  • 5,882
  • 2
  • 27
  • 39
  • 1
    +1. also the chomsly hierarchy page shows it with a nice perspective : https://en.wikipedia.org/wiki/Chomsky_hierarchy – v.oddou Aug 03 '15 at 02:39
1

There is no limitation - all finite state automata are equivalent to some regular expression, and all regular expressions are equivalent to some finite state automaton.

a p
  • 3,098
  • 2
  • 24
  • 46
1

Yes, they are equivalent. From the wikipedia page on regular languages, these are all equivalent definitions of regular languages.

  1. it is the language of a regular expression
  2. it is the language accepted by a nondeterministic finite automaton (NFA)
  3. it is the language accepted by a deterministic finite automaton (DFA)
  4. it can be generated by a regular grammar
  5. it is the language accepted by an alternating finite automaton
  6. it can be generated by a prefix grammar
  7. it can be accepted by a read-only Turing machine
  8. it can be defined in monadic second-order logic (Büchi-Elgot-Trakhtenbrot theorem)
  9. it is recognized by some finite monoid, meaning it is the preimage of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet
Robert Cooper
  • 1,270
  • 9
  • 11
1

Yes. A every finite automaton will have a corresponding regular expression. Kleene's theorem proves this result. The theorem is proved by using the principle of mathematical induction by partitioning the Finite Automata into the union of a number of smaller Finite Automatas. The proof can be found here.

Deepu
  • 7,592
  • 4
  • 25
  • 47