|
In theoretical computer science, a regular language is a formal language (i.e., a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties: Computer science (informally, CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ...
In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. ...
In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. ...
In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. ...
In automata theory, an alternating finite automaton (AFA) is a non-deterministic finite automaton whose transitions are divided into existential and universal transitions. ...
In computing, a regular expression is a string that is used to describe or match a set of strings, according to certain syntax rules. ...
In computer science a right regular grammar is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms: A → a - where A is a non-terminal in N and a is a terminal in Σ A → aB - where A and...
In computer science, a prefix grammar is a grammar, akin to the formal grammars, where strings are built up from a set of base strings by continually replacing prefixes. ...
For the test of artificial intelligence, see Turing test. ...
In logic, the monadic predicate calculus is the fragment of predicate calculus in which all predicate letters are monadic (that is, they take only one argument), and there are no function letters. ...
In mathematical logic, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. ...
Regular languages over an alphabet The collection of regular languages over an alphabet Σ is defined recursively as follows: - the empty language Ø is a regular language.
- the empty string language { ε } is a regular language.
- For each a ∈ Σ, 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.
All finite languages are regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of a's, or the language consisting of all strings of the form: several a's followed by several b's. In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ...
In mathematics, a singleton is a set with exactly one element. ...
In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. ...
A finite language is a formal language containing a finite number of strings. ...
A simple example of a language that is not regular is the set of strings  . Some additional examples are given below.
Complexity results In computational complexity theory, the complexity class of all regular languages is sometimes referred to as REGULAR or REG and equals DSPACE(O(1)), the decision problems that can be solved in constant space (the space used is independent of the input size). REGULAR ≠ AC0, since it (trivially) contains the parity problem of determining whether the number of 1 bits in the input is even or odd and this problem is not in AC0.[1] On the other hand, it is not known to contain AC0. As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ...
In computational complexity theory, a complexity class is a set of problems of related complexity. ...
DSpace is an open source software package which provides the tools for management of digital assets, and is commonly used as the basis for an institutional repository. ...
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...
AC0 is a complexity class used in circuit complexity. ...
If a language is not regular, it requires a machine with at least Ω(log log n) space to recognize (where n is the input size).[2] In other words, DSPACE(o(log log n)) equals the class of regular languages. In practice, most nonregular problems are solved by machines taking at least logarithmic space. For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...
For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ...
Closure properties The regular languages are closed under the following operations: That is, if L and P are regular languages, the following languages are regular as well: In mathematics, the closure C(X) of an object X is defined to be the smallest object that both includes X as a subset and possesses some given property. ...
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. ...
In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. ...
In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used on computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. ...
Concatenation is a standard operation in computer programming languages (a subset of formal language theory). ...
In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ...
Difference is the contrary of equality, in particular of objects. ...
Deciding whether a language is regular To locate the regular languages in the Chomsky hierarchy, one notices that every regular language is context-free. The converse is not true: for example the language consisting of all strings having the same number of a's as b's is context-free but not regular. To prove that a language such as this is not regular, one uses the Myhill-Nerode theorem or the pumping lemma. The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. ...
In formal language theory, a context-free grammar (CFG) is a grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (possibly empty). ...
In the theory of formal languages, the Myhill-Nerode theorem provides a necessary and sufficient condition for a language to be regular. ...
In the theory of formal languages, a pumping lemma states that any language of a given class can be pumped and still belong to that class. ...
There are two purely algebraic approaches to define regular languages. If Σ is a finite alphabet and Σ* denotes the free monoid over Σ consisting of all strings over Σ, f : Σ* → M is a monoid homomorphism where M is a finite monoid, and S is a subset of M, then the set f −1(S) is regular. Every regular language arises in this fashion. In abstract algebra, the free monoid on a set A is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from A, with the binary operation of concatenation. ...
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...
If L is any subset of Σ*, one defines an equivalence relation ~ (called the syntactic relation) on Σ* as follows: u ~ v is defined to mean In mathematics, an equivalence relation is a binary relation between two elements of a set which groups them together as being equivalent in some way. ...
In mathematics, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L. // Given a subset of a monoid M, one may define sets that consist of formal left or right inverses of elements in S. These are called quotients, and one...
- uw ∈ L if and only if vw ∈ L for all w ∈ Σ*
The language L is regular if and only if the number of equivalence classes of ~ is finite (A proof of this is provided in the article on the syntactic monoid). When a language is regular, then the number of equivalence classes is equal to the number of states of the minimal deterministic finite automaton accepting L. In mathematics, the syntactic monoid M(L) of a formal language L over an alphabet A is defined as the quotient M(L) = A* / ~L, where ~L denotes the syntactic congruence of L: It can be shown that the syntactic monoid of L is the smallest monoid that recognizes L...
A similar set of statements can be formulated for a monoid  . In this case, equivalence over M leads to the concept of a recognizable language. In mathematics and computer science, a recognizable language is a formal language that is recognized by a finite state machine. ...
Finite languages A specific subset within the class of regular languages is the finite languages - those containing only a finite number of words. These are obviously regular as one can create a regular expression that is the union of every word in the language, and thus are regular. In computing, a regular expression is a string that is used to describe or match a set of strings, according to certain syntax rules. ...
In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...
See also In the theory of formal languages, the pumping lemma for regular languages is a lemma that gives a property that all regular languages have. ...
References - Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Chapter 1: Regular Languages, pp.31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.
- ^ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
- ^ J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations. Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, pp. 179–190. 1965.
Michael Sipser Michael Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. ...
External links - Department of Computer Science at the University of Western Ontario: Grail+, http://www.csd.uwo.ca/Research/grail/. A software package to manipulate regular expressions, finite-state machines and finite languages. Free for non-commercial use.
- Chalchalero! http://www.ucse.edu.ar/fma/sepa/chalchalero.htm. A free visual software to manipulate regular expressions, regular grammars, finite-state machines and finite languages developed by the SEPa! Project Team (Universidad Católica de Santiago del Estero).
|
of L
of L and P
of L and P
of L and P
Feeds |
Contact