0
$\begingroup$

According to the answer provided by Janoma, there are several methods to determine the regularity of a language.

Theorem

Let L ⊆ Σ∗. The following conditions are equivalent:

  • L is generated by a regular expression (i.e., the definition of regular language).
  • L is recognized by a nondeterministic finite automaton (Kleene).
  • L is recognized by a nondeterministic finite automaton without ε-transitions.
  • L is recognized by a deterministic finite automaton (Scott and Rabin).
  • L is generated by a grammar (N, Σ, P, S), where N is a finite subset of Σ∗ (Frazier and Page).
  • L is generated by a left (resp. right) regular context-free grammar.
  • The index of the Nerode relation ≡L is finite (Anil Nerode, Linear automaton transformations, 1958). This is widely (and incorrectly) known as the Myhill-Nerode theorem. ≡L is the relation used to build the minimal DFA of a regular language.
  • The index of the Myhill relation ∼L is finite (John Myhill, Finite Automata and the Representation of Events, 1957). ∼L is the relation used to build the syntactic monoid of an arbitrary language.
  • The syntactic monoid of L is finite (consequence of Myhill's result). We note here that the syntactic monoid, apart from being defined by using relation ∼L, can be defined as a minimal monoid (in size) that recognizes L as a preimage of a homomorphism.
  • L can be recognized by a read-only Turing Machine (trivial).
  • L can be defined by a formula in Monadic second-order logic over strings (Büchi).

However, in none of these methods is there a clear, step by step process that can be followed to conclusively prove that a language is regular.

Does such an algorithm exist? Please provide the necessary references as well.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ What would be the input of the algorithm? $\endgroup$
    – Steven
    Feb 22 at 17:23
  • $\begingroup$ It is not "trivial" that a read-only Turing machine accepts only regular languages. Note a TM may move in two directions. Also excursions into the empty part of the tape have to be accounted for. $\endgroup$
    – Hendrik Jan
    Feb 22 at 18:27
  • $\begingroup$ @Steven I would assume the grammar of that language. $\endgroup$
    – Alan Whitteaker
    Feb 26 at 13:17

1 Answer 1

Reset to default
3
$\begingroup$

Of course one would first have to specify the language to apply the regularity algorithm. Even for a rather restricted class of language specifications such an algorithm would be impossible.

It is undecidable, for a given context-free grammar, to decide whether it accepts a regular language.

Theorem 6.3 (c) in: Bar-Hillel, Perles, Shamir, On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung 14 (1961) 143–172. doi 10.1524/stuf.1961.14.14.143

Improve this answer
$\endgroup$
1
  • $\begingroup$ The quoted reference has been OCR'ed at the publisher as "On formai properties oî simple phreise structure grammars". Moreover, it claims: Published Online: 1961-04. $\endgroup$
    – Hendrik Jan
    Feb 22 at 18:36

Your Answer

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

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