• Wilfrid Laurier University

• CP 414

CP414 Test 1

Table of Contents

CP414 Test 1.............................................................................................................................. 1

1.1 Finite Automata..................................................................................................................... 1

Formal Definition of a Finite Automata................................................................................................ 2

Formal Definition of Computation......................................................................................................... 4

Designing Finite Automata........................................................................................................................ 4

The Regular Operations.............................................................................................................................. 5

1.2 Nondeterminism................................................................................................................... 6

Formal Definition of a Nondeterministic Finite Automaton........................................................7

Equivalence of NFAs and DFAs................................................................................................................. 7

Closure under the regular operations................................................................................................... 8

1.3 Regular Expressions............................................................................................................ 8

Equivalence with Finite Automata....................................................................................................... 10

1.4 Nonregular Languages...................................................................................................... 14

The Pumping Lemma................................................................................................................................ 14

1.1 Finite Automata

- FA are good models for computers with limited amount of memory

- e.g. of computers with small memory: controller for an automatic door

- FA and Markov chains are useful tools when attempting to recognize patterns in data

Finite automation, M1:



- This is the state diagram

- There are three states: q1, q2, q3

- Start state: q1, indicated by arrow pointing at it from nowhere

- Accept state: q2, one with the double circle

- Transitions: arrows going from one state to another

- When this automation receives and input i.e. 1101, it processes that string

and produces an output

- the output is either Accept or Reject

- e.g. feed input string 1101:

1. Start in state q1

2. Read 1, follow transition from q1 to q2

3. Read 1, follow transition from q2 to q2

4. Read 0, follow transition from q2 to q3

5. Read 1, follow transition from q3 to q2

6. Accept, because M1 is in an accept state q2 at beginning of the input

- M1 accepts any string that ends with 1, as it goes to its accept state q2,

whenever it reads symbol 1

- It also accepts 100, 0100, and any string that ends with even number of 0s

following the last 1

Formal Definition of a Finite Automata

- need a formal definition for 2 reasons:

o It is precise, resolves any uncertainties

o Provides notation

- FA has several parts:

o Set of states and rules for going from one state to another

o Input alphabet that indicates the allowed input symbols

o Start state and set of accept states

o FA is defined to be a 5-tuple consisting of these 5 parts

- Use transition function δ to determine rules for moving

- If the FA has an arrow from a state x to a state y labeled with input symbol 1,

if the FA is in state x when it reads 1, then it moves to state y

o can also indicate this by: (x, 1) = y δ

Returning to example M1: