PlanetMath: regular language

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (198)
Orphanage
Unclass'd
Unproven (498)
Corrections (24)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

regular language

(Definition)

A regular grammar is a context-free grammar where all productions must take one of the following forms (specified here in BNF, $\lambda$ is the empty string):

$\displaystyle \verb.<.\textit{non-terminal}\verb.>.$	$\displaystyle ::=$	$\displaystyle terminal$
$\displaystyle \verb.<.\textit{non-terminal}\verb.>.$	$\displaystyle ::=$	$\displaystyle terminal\,\verb.<.\textit{non-terminal}\verb.>.$
$\displaystyle \verb.<.\textit{non-terminal}\verb.>.$	$\displaystyle ::=$	$\displaystyle \lambda$

A regular language (also known as a regular set or a regular event) is the set of strings generated by a regular grammar. Regular grammars are also known as Type-3 grammars in the Chomsky hierarchy.

A regular grammar can be represented by a deterministic or non-deterministic finite automaton. Such automata can serve to either generate or accept sentences in a particular regular language. Note that since the set of regular languages is a subset of context-free languages, any deterministic or non-deterministic finite automaton can be simulated by a pushdown automaton.

There is also a close relationship between regular languages and regular expressions. With every regular expression we can associate a regular language. Conversely, every regular language can be obtained from a regular expression. For example, over the alphabet $\lbrace a,b,c\rbrace$ , the regular language associated with the regular expression $a(b\cup c)^*a$ is the set

$\displaystyle \lbrace a\rbrace \circ \lbrace b,c\rbrace^* \circ \lbrace a\rbrace=\lbrace awa\mid w$ is a word in two letters $\displaystyle b$ and $\displaystyle c\rbrace,$

where $\circ$ is the concatenation operation, and

is the Kleene star operation. Note that

could be the empty word $\lambda$ .

Yet another way of describing a regular language is as follows: take any alphabet $\Sigma$ . Let $\mathcal{R}(\Sigma)$ be the smallest subset of $P(\Sigma^*)$ (the power set of the set of words over $\Sigma$ , in other words, the set of languages over $\Sigma$ ), among all subsets of $P(\Sigma^*)$ with the following properties:

$\mathcal{R}(\Sigma)$ contains all sets of cardinality no more than 1 (i.e., $\varnothing$ and singletons);
$\mathcal{R}(\Sigma)$ is closed under set-theoretic union, concatenation, and Kleene star operations.

Then

is a regular language over $\Sigma$ iff $L\in \mathcal{R}(\Sigma)$ .

"regular language" is owned by mps. [ full author list (3) | owner history (1) ]

(view preamble)

Other names:

regular grammar, Type-3 grammar, regular set, regular event

Keywords:

regular expression, Chomsky

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: iff, union, closed under, singletons, cardinality, contains, properties, languages, power set, empty word, Kleene star, operation, concatenation, alphabet, associate, regular expressions, pushdown automaton, subset, sentences, generate, automata, non-deterministic finite automaton, Chomsky hierarchy, generated by, strings, empty string, BNF, productions, context-free grammar
There are 15 references to this entry.

This is version 13 of regular language, born on 2002-02-23, modified 2007-11-09.
Object id is 2548, canonical name is RegularLanguage.
Accessed 12652 times total.

Classification:

AMS MSC:	68Q45 (Computer science :: Theory of computing :: Formal languages and automata)
	68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

No messages.

Interact