AL102 - PRELIM

an exciting, theoretical branch of computer science. It established its roots during the 20th Century, as mathematicians began developing - both theoretically and literally - machines which imitated certain features of man, completing calculations more quickly and reliably.

Automata Theory

closely related to the word "automation", denotes automatic processes carrying out the production of specific processes. Simply stated, automata theory deals with the logic of computation with respect to simple machines, referred to as

Automaton

Through _, computer scientists are able to understand how machines compute functions and solve problems and more importantly, what it means for a function to be defined as COMPUTABLE or for a question to be described as DECIDABLE.

Automata

CHARACTERISTICS OF MACHINES

1. Input

2. Output

3. States

FOUR MAJOR FAMILIES OF AUTOMATON

1. finite-state machine

2. pushdown automata

3. linear-bounded automata

4. Turing Machine

two neurophysiologists, were the first to present a description of finite automata in 1943. Their paper, entitled, "A Logical Calculus Immanent in Nervous Activity",

Warren McCulloch and Walter Pitts

generalized the theory to much more powerful machines in separate papers, published in 1955-56.

G.H. Mealy, E.F. Moore

An automaton in which the state set Q contains only a finite number of elements. These are abstract machines, consisting of a set of states (set Q), set of input events (set I), a set of output events (set Z) and a state transition function.

finite-state machine

5 - Tuples of Finite State Machine

Q = finite set of states

I = finite set of input symbols

Z = finite set of output symbols

∂ = mapping of I x Q into Q called the state transition

function, i.e. I x Q → Q

W = mapping W of I x Q onto Z, called the output function

A = set of accept states where F is a subset of Q

World-renowned computer scientist conceived the first "infinite" (or unbounded) model of computation: to solve the Entscheindungsproblem.

Alan Turing

a collection of things

Set

We combine the elements of the two sets.

Union

is when you must be in BOTH sets.

intersection

You can also "subtract" one set from another.

Difference

the set that has everything.

Universal Set

"everything that is not"

Complement

the set with no elements.

Empty Set

STEPS IN SOLVING WORLD PROBLEMS

1. Read the problem

2. Identify and list the facts

3. Figure out exactly what the problem is asking for

4. Eliminate excess information

5. Pay attention to units of measurement

6. Draw a diagrap

7. Find or develop a formula

8. Consult a reference

9. Do the math and check your answer

an entity or individual objects, which can be any letter, alphabet or any picture.

Symbols

are a finite set of symbols. It is denoted by ∑.

Alphabets

It is a finite collection of symbols from the alphabet.

String

are used to recognize patterns. It takes the string of symbol as input and changes its state accordingly. When the desired symbol is found, then the transition occurs.

Finite Automata

TYPES OF AUTOMATA

DFA - Deterministic Finite Automata (uniqueness)

NFA - Non-deterministic Finite Automata (accepts null)

is a directed graph which can be constructed as follows:

•There is a node for each state in Q, which is represented by the circle.

• There is a directed edge from node q to node p labeled a if δ(q, a) = p.

• In the start state, there is an arrow with no source.

• Accepting states or final states are indicating by a double circle.

Transition Diagram