1
$\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.

$\endgroup$
4
  • 3
    $\begingroup$ What would be the input of the algorithm? $\endgroup$
    – Steven
    Commented Feb 22, 2023 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$ Commented Feb 22, 2023 at 18:27
  • $\begingroup$ @Steven I would assume the grammar of that language. $\endgroup$ Commented Feb 26, 2023 at 13:17
  • $\begingroup$ @AlanWhitteaker that assumption should be added to the actual question. $\endgroup$
    – Kai
    Commented May 14 at 0:21

2 Answers 2

6
$\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

$\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$ Commented Feb 22, 2023 at 18:36
0
$\begingroup$

A subset $L ⊆ Σ^*$ is regular if and only if $q_L = \{ w \backslash L: w ∈ Σ^* \}$ is finite. The left-quotient is defined by $$ w ∈ Σ^*, L ⊆ Σ^* ↦ w \backslash L = \{ w' ∈ Σ^*: w w' ∈ L \}, $$ and satisfies the properties $$ε \backslash L = L,\quad (w w') \backslash L = w' \backslash (w \backslash L),$$ where $ε ∈ Σ^*$ denotes the empty word.

Whether $L$ is regular or not, the state diagram given by the transitions $A \overset{x}→ x \backslash A$, for $x ∈ Σ$ and $A ⊆ Σ^*$, whose final states are all $A ∋ ε$, contains the state diagrams of the minimal deterministic automaton of every $L ⊆ Σ^*$: it is The Universal State Diagram.

The set of "states" in the diagram accessible from a given $L ⊆ Σ^*$ is just $q_L$, itself, the state set is finite precisely when $L$ is regular and the portion of the state diagram containing $q_L$ with $L$ designated as the start state is the minimal deterministic finite state automaton for $L$. Otherwise if $L$ is not finite, then the automaton is an infinite state automaton - but still deterministic - and may or may not be recursively specifiable.

$\endgroup$

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.