*
Share This
Formal language table
table started by
pumpkin for the Computer Science Base
There is no user-contributed description yet.
x
Add another type with the property you want to view.
| x name | x image | x Automaton recognizing | x article |
|---|---|---|---|
| x Recursively enumerable language | Turing machine |
In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-recognizable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...
|
|
| x Regular language |
|
Deterministic finite state machine |
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:
The collection of regular languages...
|
| Nondeterministic finite state machine | |||
| x Context-free language | Pushdown automaton |
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.
An archetypical context-free language...
|
|
| x Deterministic context-free language | Deterministic pushdown automaton |
A deterministic context-free language is a formal language which is defined by a deterministic context-free grammar. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic...
|
|
| x Star-free language | Aperiodic finite state automaton |
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, boolean operators and concatenation but no Kleene star. For instance, the language of words...
|
|
| x Mildly context-sensitive language | Embedded pushdown automaton |
In formal grammar theory, mildly context-sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced by...
|
|
| x Indexed language | Nested stack automaton |
Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automatons. .
Indexed languages are a proper subset of context-sensitive languages and a proper...
|
|
| x Context-sensitive language | Linear bounded automaton |
In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used, in...
|
|
| x Recursive language | Decider |
A recursive language in mathematics, logic and computer science is a type of formal language which is also called decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP...
|
|
| x Omega-regular language | Büchi automaton |
The omega-regular languages are a class of omega languages which generalize the definition of regular languages to infinite words.
An omega-language L is omega-regular if it has the form
Every omega-regular language is accepted by a nondeterministic...
|
|
