Regular Formal Language

Jump to navigation Jump to search

A Regular Formal Language is a context-free formal language that can be generated by a regular grammar (Type-3 grammars).



  1. M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science 2500, Springer 2002.


    • The collection of regular languages over an alphabet Σ is defined recursively as follows:
      • The empty language Ø is a regular language.
      • For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language.
      • If A and B are regular languages, then A ∪ B (union), A • B (concatenation), and A* (Kleene star) are regular languages.
      • No other languages over Σ are regular.
    • See regular expression for its syntax and semantics. Note that the above cases are in effect the defining rules of regular expression.