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:
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
it can be generated by a regular grammar
it can be accepted by a read-only Turing machine
In next post, I will discuss formal definition of deterministic finite state machine (DFA). DFA is my Favorite topic.
I am sure you will also like it when we will discuss it in detail after completing all formal definitions.
Showing posts with label turing machines. Show all posts
Showing posts with label turing machines. Show all posts
Saturday, May 12, 2007
Subscribe to:
Posts (Atom)