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.