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).
- Context:
- It can expressed using a regular expression over alphabet Σ.
- It can be accepted by a Finite State Automaton (nondeterministic finite automaton, deterministic finite automaton, alternating finite automaton).
- It can be generated by a Grammar, such as a: Regular Grammar and a Prefix Grammar.
- It can be accepted by a read-only Turing machine.
- It can be defined in monadic second-order logic (Büchi-Elgot-Trakhtenbrot theorem[1])
- It is recognized by some finite monoid, meaning it is the preimage of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet (see Myhill–Nerode theorem).
- See: Regular Expression Pattern.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/regular_language Retrieved:2015-6-7.
- In theoretical computer science and formal language theory, a regular language (also called a rational language ) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science. (Many regular expressions engines provided by modern programming languages are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression.)
Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem. In the Chomsky hierarchy, regular languages are defined to be the languages that are generated by Type-3 grammars (regular grammars).
Regular languages are very useful in input parsing and programming language design.
- In theoretical computer science and formal language theory, a regular language (also called a rational language ) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science. (Many regular expressions engines provided by modern programming languages are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression.)
- ↑ 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.
2013
- http://en.wikipedia.org/wiki/Regular_language#Formal_definition
- 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.
- The collection of regular languages over an alphabet Σ is defined recursively as follows: