CS计算机代考程序代写 algorithm FIT2014 Theory of Computation Lecture 7 Finite Automata

FIT2014 Theory of Computation Lecture 7 Finite Automata

Monash University
Faculty of Information Technology

FIT2014 Theory of Computation

Lecture 7
Finite Automata

slides by Graham Farr
based in part on previous slides by David Albrecht

COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969

Warning
This material has been reproduced and communicated to you by or on behalf of Monash University

in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.

Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.

1 / 26

Overview

I Definition

I How they are used to define languages

I Representations

I Complement Languages

I Comparison with Regular Expressions

2 / 26

Finite Automaton (FA)

I Sometimes known as a Deterministic Finite Automaton (DFA).

I Used for determining whether a word does or does not belong to a Regular
Language.

I Used for defining a Regular Language.

I Used in Lexical Analysers.

3 / 26

Notation and terminology . . . and Alternative notation

a

b

a,bb

a

a

b

a,bb

a

states,
represented as vertices.
Special states:

I Start State

I Final State

transitions,
represented as directed edges,
labelled by letters

+

a

b

a,bb

a
4 / 26

Finite automaton: definition

I A finite set of states
I One called the Start State
I Some (maybe none) called Final States

I An alphabet of possible input letters

I A finite set of transitions

I that tell, for each state and each letter in the alphabet, which state to go to next.
I There is a unique transition from any state for each letter in the alphabet.

5 / 26

Finite automaton: representations

1

2

3

a

b

a,bb

a

a b

Start 1 1 2
2 3 3

Final 3 3 2

6 / 26

Finite automata

Every string traces a unique path in the automaton, starting from the Start State and
following the transitions, letter by letter.

7 / 26

1

2

3

a

b

a,bb

a

a b

Start 1 1 2
2 3 3

Final 3 3 2

8 / 26

Finite automata

Algorithm 1: Execution of a Finite Automaton

Input: a string

Begin at the Start State.
while there is another input letter do

Read the next letter of the input string.
Move along the directed edge labelled by this letter.

if you’re in a Final State then
Accept input string.

else
Reject input string.

9 / 26

Finite automata

Every string traces a unique path in the automaton, starting from the Start State and
following the transitions, letter by letter.

Definitions
A string is accepted by a FA if its path ends on a Final State.
Otherwise the string is rejected.
The language recognised by a FA is the set of all strings it accepts.
We say the FA recognises the language, or accepts the language.

10 / 26

Finite automata

1

2

3

a

b

a,bb

a

a b

Start 1 1 2
2 3 3

Final 3 3 2

11 / 26

1

2

3

4

5

a

b

ba ba

a

b

a

b

a b

Start 1 2 3
2 4 3
3 2 5

Final 4 4 5
Final 5 4 5

12 / 26

Special Cases

I All words accepted.

I No words accepted.

I Only the empty word accepted.

I Only non-empty words accepted.

I A single word accepted.

13 / 26

Complements
If L is a language over an alphabet, then its complement L is the set of words over
the alphabet that are not in L.

L = Σ∗ \ L
The complement of L is sometimes denoted by L′ or Lc .

Examples

∅ = Σ∗ Σ∗ = ∅ {words of ≤ 3 letters} = {words of ≥ 4 letters}

EVEN-EVEN := { strings that contain an even number of a’s and an even number of b’s }
= { ε, aa, bb, aaaa, aabb, abab, abba, baab, . . . }.

EVEN-EVEN := { strings which contain an odd number of a’s or an odd number of b’s }
= { a, b, ab, ba, aaa, aab, aba, abb, baa, . . . }

14 / 26

EVEN-EVEN
b

b

aa aa

b

b
15 / 26

Complement Finite Automaton (FA)

Suppose some FA accepts the language L.

Change all the final states in this FA to non-final states,
and all the non-final states to final states.

This new FA now accepts all the strings not accepted by the original FA
(i.e., all the words in L),

and rejects all the words that the original accepted
(i.e., the words in L).

So the new FA accepts L.

16 / 26

EVEN-EVEN
b

b

aa aa

b

b
17 / 26

Comparison with Regular Expressions

It is (usually) easier
to write down a regular expression that defines a language

than
to design a FA to accept this language.

It is easier
to check whether a given string is accepted by a FA

than
to see whether it matches a regular expression.

It is easier
to find complements using a FA

than
by using a regular expression.

18 / 26

Some Generalizations of Finite Automata

This week:

I It is not required that, for every state and letter, there is a unique transition.

I It can change state without reading a letter.

I It can read more than one letter at a time.

Next week:

I It can read strings which match regular expressions, not just single letters.

Later:

I Each transition can produce output letters as well as changing state. (transducer)

I Transitions can read and write letters from some kind of memory.

I For a given state and letter, the next state is chosen probabilistically.

19 / 26

Nondeterministic Finite Automaton (NFA)

NFA are defined like a Finite Automaton (FA) except for transitions.

Transitions

I For some states and letters there is a transition.

I The labels may include the empty word ε.

So for a given letter and state there may be:

I No transition

I More than one transition

For a given string, the path it takes . . .

I might not exist

I might not be unique

20 / 26

aba

a b a

b

a b

a,b

a,b

FA

sink state

a b a
NFA

21 / 26

ab ∪ abb ∪ baa

a b b

a

b

b

a a

22 / 26

Is abbbabbbabba accepted?

a a,b

a

bb

aa

b

a

b

a b

a

b

23 / 26

Properties

I If there is no transition for the current letter and state the machine crashes.
I Paths from the Start State to a Final State for a given input:

I One
I None
I Several (Nondeterministic)

I Accept a string if there is at least one path from the Start State to a Final State.

I Reject a string if there are no paths from the Start State to a Final State.

24 / 26

a(aa ∪ bb)∗b

a ε

a

b

a

b

ε b

ε

ε

25 / 26

Revision

Finite Automata (FA)

I Definition. How to use them.

I How to construct a Finite Automaton to accept a language.

Complement Languages

I What they are. Designing FA to accept them.

Nondeterministic Finite Automata (NFA)

I Definition. How to use them

I How to construct a Nondeterministic Finite Automaton to accept a language.

Reading: Sipser Ch 1.

26 / 26