1
$\begingroup$

Languages recognized by finite automata are exactly those definable by sentences of the sequential calculus, and also exactly those definable by rational expressions (also called regular expressions)

Howard Straubing, Pascal Weil. An introduction to finite automata and their connection to logic. Deepak D’Souza, Priti Shankar. Modern applications of automata theory, World Scientific, pp.3-43, 2012, IISc Research Monographs. hal-00541028v2

Can you please explain, what is the connection between finite automata and sequential calculus (logic)?

Improve this question
$\endgroup$
3
  • $\begingroup$ sequential calculus = regular expressions ? $\endgroup$
    – nir shahar
    May 6, 2021 at 8:34
  • $\begingroup$ @nirshahar sequential calculus != regular expressions. I have updated the question. $\endgroup$
    – Oleg Dats
    May 6, 2021 at 9:13
  • 1
    $\begingroup$ The sequential calculus that is treated here is Büchi's calculus of monadic second order logic. Both automata and this logic define the regular languages, like is stated in the quote in your question. Please secify your question. $\endgroup$
    – Hendrik Jan
    May 6, 2021 at 12:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.