0
$\begingroup$

I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression.

In my current understanding the rule is "L is acceptable by Automaton <=> L is rational"

But does that automatically mean that for every regular L there is also a regular expression?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Yes. This the "French terminology". Elsewhere you might encounter it as regular expressions, and the theorem is that the set of regular languages (i.e. those defined by regular expressions) is the same as the class of languages recognized by DFAs. $\endgroup$
    – Shaull
    Commented Nov 16, 2021 at 14:41
  • $\begingroup$ Do I understand your question correctly: you want to know if there exists a rational expression for every possible language (for a fixed alphabet)? When you say "recognizable", do you mean Turing-recognizable? $\endgroup$
    – kviiri
    Commented Nov 16, 2021 at 14:51
  • $\begingroup$ @kviiri I'm a bit confused because I'm german and the translation is confusing but by "recognizable" I mean that the Automaton "accepts" words of the language and therefore there's a run for a word w∈A $\endgroup$
    – Ferris
    Commented Nov 16, 2021 at 14:58
  • $\begingroup$ @Ferris Thank you for the clarification :) I will answer to the best of my ability. $\endgroup$
    – kviiri
    Commented Nov 16, 2021 at 15:02

1 Answer 1

Reset to default
2
$\begingroup$

Every rational language can be represented by (at least one) rational expression, and every rational expression represents a rational language. That means for any rational language, you can find the equivalent expression (though it might not always be a simple task). In fact, there are algorithms that convert any NFA into an equivalent rational expression and vice versa, proving their equal expressive power: for example the McNaughton-Yamada-Thompson algorithm for converting a rational expression to an NFA and Kleene's algorithm for converting an NFA to a rational expression.

Rational expressions and languages are usually referred to as "regular" in English, but the word "rational" is also used. Be careful with the term "recognizable", however, because it is usually taken to mean "Turing-recognizable" in English discourse in automata theory – these languages form a much larger group than rational languages, and include many non-rational languages.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ thank you so much. I can imagine this now by a surjective set from the regular languages pointing into regular expressions. This explains a lot for me and I will look further into this topic now :) $\endgroup$
    – Ferris
    Commented Nov 16, 2021 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.