Regular Language

it can be accepted by a Deterministic Finite State Machine

it can be accepted by a Nondeterministic Finite State Machine

it can be accepted by an Alternating Finite Automaton

it can be described by a Regular Expression . Note that the "regular expression" features provided with many programming languages are augmented with features that make them capable of recognizing languages which are not regular.

it can be generated by a Regular Grammar

it can be generated by a Prefix Grammar

it can be accepted by a read-only Turing Machine

it can be defined in Monadic Second-order 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 Language s 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.

A simple example of a language that is not regular is the set of strings

\{a^nb^n\,ert\; n\ge 0\}

. Some additional examples are given below.

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). 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 .

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:

the Complement $\bar{L}$ of ''L''

the Kleene Star $L^---$ of ''L''

the image ''φ(L)'' of ''L'' under a String Homomorphism

the Concatenation $L \circ P$ of ''L'' and ''P''

the Union $L \cup P$ of ''L'' and ''P''

the Intersection $L \cap P$ of ''L'' and ''P''

the Difference $L-P$ of ''L'' and ''P''

the reverse $L^R$ of ''L''

DECIDING WHETHER A LANGUAGE IS REGULAR

To locate the regular languages in the or the Pumping Lemma .

denotes the where ''M'' is a ''finite'' monoid, and ''S'' is a subset of ''M'', then the set ''f''⁻¹(''S'') is regular. Every regular language arises in this fashion.

, one defines an Equivalence Relation ~ (called the Syntactic Relation ) on Σ--- as follows: ''u'' ~ ''v'' is defined to mean

Syntactic Monoid

Minimal Deterministic Finite Automaton

. In this case, equivalence over ''M'' leads to the concept of a Recognizable Language .

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.

SEE ALSO

Pumping Lemma For Regular Languages

REFERENCES

¹ Chapter 1: Regular Languages, pp.31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.

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).

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT REGULAR LANGUAGE

	formal languages

Information About

Regular Language