# Introduction to the theory of computation, michael sipser, chapter 1: regular languages

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}