Chapter 1: Regular Languages
Introduction:
· An idealized computer is called a “computational model” which allows us to set up a manageable
Mathematical theory of it directly.
· As with any model in science, a computational model may be accurate in some ways but perhaps not
In others.
· The simplest model is called “finite state machine” or “finite automaton”.
Finite Automata:
· Finite Automata are good models for computers with an extremely limited amount of memory, like for
Example an automatic door, elevator or digital watches.
· Finite automata and their probabilistic counterpart “Markov chains” are useful tools when we are
Attempting to recognize patterns in data. These devices are used in speech processing and in optical
Character recognition. Markov chains have even been used to model and predict price changes in
Financial markets.
· State diagrams are described
· The output of an finite automaton is “accepted” if the automaton is now in an accept state (double
Circle) and reject if it is not.
· A finite automaton is a list of five objects:
O Set of states
O Input alphabet
O Rules for moving
O Start state
O Accepts states
· d (x,1) = y, means that a transition from x to y exists when the machine reads a 1.
· Definition: A finite automaton is a 5 – tuple ( , , , , ) 0 Q S d q F, where
1. Q is a finite set called the states.
2. S is a finite set called the alphabet.
3. d :Q´ S ®Q is the transition function
4. q ÎQ 0 is the start state
5. F Í Q is the set of accept states.
· If A is the set of all strings that machine M accepts, we say that A is the language of machine M and
Write L(M) = A. We say M recognizes A.
/>
· A language is called a “regular language” if some finite automaton recognizes it.
· A finite automaton has only a finite number of states, which means a finite memory.
· Fortunately, for many languages (although they are infinite) you don’t need to remember the entire
Input (which is not possible for a finite automaton). You only need to remember certain crucial
Information.
The Regular Operations:
· We define 3 operations on languages, called the regular operations, and use them to study properties of
The regular languages.
· Definition: Let A and B be languages. We define the regular operations union, concatenation and
Star as follows:
O Union: AÈ B = {x | xÎ A or xÎ B}
O Concatenation: Ao B = {xy | xÎ A and y Î B}
O Star: * { … | 0 } 1 2 A x x x k and each x A k i = & sup3; Î
· Example: Let the alphabet S be the standard 26 letters {a, b, …, z}. If language A = {good, bad} and
Language B = {boy, girl}, then:
O AÈ B = {good, bad, boy, girl}
O Ao B = {goodboy, goodgirl, badboy, badgirl}
O A* = {e, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbas, …}
· The class of regular languages is closed under the union operation. In other word, if A and B are
Regular languages, so is AÈ B.
· The class of regular languages is closed under the concatenation operation.
· The class of regular languages is closed under the intersection operation.
· The class of regular languages is closed under the star operation.
Nondeterminism:
· Nondeterminism is a generalization of determinism, so every deterministic finite automaton is
Automatically a nondeterministic finite automaton.
· In a DFA (deterministic finite automaton), every state always has exactly one exiting transition arrow
For each symbol in the alphabet.
(No Ratings Yet)