[Home]History of Regular language

HomePage | Recent Changes | Preferences

Revision 10 . . November 9, 2001 6:57 am by AxelBoldt [+Grail; emphasize equivalent definitions.]
Revision 9 . . November 9, 2001 6:38 am by AxelBoldt [+shuffle operation, right and left quotients]
Revision 7 . . November 9, 2001 5:25 am by BenBaker
  

Difference (from prior major revision) (author diff)

Changed: 1,3c1,6
A regular language is a formal language (i.e. a possibly infinite set of finite sequences of symbols from a finite alphabet) that can be accepted by a deterministic finite state automaton.

Equivalent ways of describing regular languages are deterministic and non-deterministic finite automata, regular grammars, read-only Turing machines and regular expressions.
A regular language is a formal language (i.e. a possibly infinite set of finite sequences of symbols from a finite alphabet) that has one of the following equivalent properties:
* it can be accepted by a deterministic finite state automaton.
* it can be accepted by a non-deterministic finite automaton
* it can be generated by a regular grammar
* it can be accepted by a read-only Turing machine
* it can be described by a regular expression.

Added: 15a19,22



External resources:
* 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.

HomePage | Recent Changes | Preferences
Search: