CS计算机代考程序代写 algorithm FIT2014 Theory of Computation Lecture 9 Kleene’s Theorem. II. FA -3mu Regexp

FIT2014 Theory of Computation Lecture 9 Kleene’s Theorem. II. FA -3mu Regexp

Monash University
Faculty of Information Technology

FIT2014 Theory of Computation

Lecture 9
Kleene’s Theorem. II.

FA −→ Regexp

slides by Graham Farr

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 / 23

Overview

Previous lecture:

I Convert Regular Expressions to NFA

I Convert NFA to FA

Today:

I Generalised Nondeterministic Finite Automata

I Convert FA to GNFA

I Convert GNFA to Regular Expression

2 / 23

Kleene’s Theorem

Regular Expression NFA

Finite AutomatonGNFA

3 / 23

Generalised Nondeterministic Finite Automaton (GNFA)

Definitions
A Generalised Nondeterministic Finite Automaton (GNFA) is defined as for an
NFA except that transitions may be labelled by regular expressions, not just by single
letters.

A string w is accepted by a given GNFA if it can be divided into substrings,
w = w1 · · ·wk , such that there is some sequence of transitions, starting at the Start
State, finishing at the Final State, and labelled by regular expressions R1, . . . ,Rk , such
that, for all i , wi matches Ri .

If a string w is not accepted by the GNFA, then it is rejected.

4 / 23

Standard GNFA

A standard GNFA is a GNFA in which:

I there is just one Final State, and it is not the Start State;

I the Start State has no incoming transitions and the Final State has no outgoing
transitions.

Notes:

I Sometimes (e.g., in Sipser), standard GNFAs are required to have arcs going
between every pair of states, subject to the prohibition on incoming arcs into the
Start State and outgoing arcs from the Final State. If a transition actually cannot
occur between two states, then the arc between them is labelled by the regular
expression ∅, which prevents the transition from being used.

I This is not really needed, for the algorithm we will describe. But it may make
proving properties of that algorithm easier.

I Standard GNFAs are sometimes called GNFAs of “special form” in Sipser.

5 / 23

From FA to Standard GNFA

Given a FA (or an NFA):

1. Ensure there is a single Final State, with incoming arcs only.
I If necessary: add new Final State, add new transitions labelled ε from the previous

Final States to this new one, and make those states no longer Final.

2. Ensure there is a single Start State, with outgoing arcs only.
I If necessary: add a new Start State, add new transitions labelled ε from this new

Start State to the previous Start States, and make those states no longer Start
states.

The letters on the arcs of the FA/NFA are already regular expressions in their own
right.

The GNFA constructed by this process accepts the same language as the original FA.

6 / 23

Kleene’s Theorem

Regular Expression NFA

Finite AutomatonGNFA

7 / 23

From Standard GNFA to Regular Expression

Starting with a Standard GNFA, we convert it to an equivalent GNFA with one fewer
state.

We keep doing this until we have a GNFA with just a Start State, a Final State, and
one transition:

R

The regular expression R on this transition defines the same language as the original
GNFA.

8 / 23

From GNFA to Regular Expression

Notation:
q some non-Start, non-Final state.
qin any non-Final state.
Rin the regular expression on the transition from qin to q.
qout any non-Start state.
Rout the regular expression on the transition from q to qout.
Rloop the regular expression on the transition from q to itself.
Rdirect the regular expression on the transition from qin to qout.

9 / 23

From GNFA to Regular Expression

qin qout

q

Rdirect

Rin Rout

Rloop

qin qout

q

Rdirect ∪ (RinR∗loopRout)

Rin Rout

Rloop

10 / 23

From GNFA to Regular Expression

Ensure this replacement is done for all qin, qout.

Then q is removed, and we have an equivalent GNFA to the one we started with.

Keep doing this whole procedure, removing one state at a time, until you are left with
just the Start State and the Final State, with a single transition between them.

The regular expression on this transition is the one you want.

It matches precisely those strings accepted by the original GNFA.

Examples: Sipser, pp. 75–76.

11 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b∪ (aa∗a)

a

a

a

b
ε

b

b

12 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b ∪ (aa∗a)

a

a

a

b
ε

b

b∪ (ba∗a)
13 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b ∪ (aa∗a)

a

a

a

b
ε∪ (ba∗b)

b

b ∪ (ba∗a)
14 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b ∪ (aa∗a)

a∪ (aa∗b)

a

a

b
ε ∪ (ba∗b)

b

b ∪ (ba∗a)
15 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b ∪ (aa∗a)

a ∪ (aa∗b)

a

a

b
ε ∪ (ba∗b)

b

b ∪ (ba∗a)
16 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b ∪ (aa∗a)

a ∪ (aa∗b)

a

a

b
ε ∪ (ba∗b)

b

b ∪ (ba∗a)
17 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b ∪ (aa∗a)

a

a

b
ε ∪ (ba∗b)

b

b ∪ (ba∗a)

a ∪ (aa∗b)
∪ ((b ∪ (aa∗a))(b ∪ (ba∗a))∗(ε ∪ (ba∗b)))

18 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b ∪ (aa∗a)

a

a

b
ε ∪ (ba∗b)

b

b ∪ (ba∗a)

a ∪ (aa∗b)
∪ ((b ∪ (aa∗a))(b ∪ (ba∗a))∗(ε ∪ (ba∗b)))

19 / 23

From GNFA to Regular Expression

1

2

3

4

a

b

a

a

a

b
ε

b

b

1

2

3

4

a

b ∪ (aa∗a)

a

a

b
ε ∪ (ba∗b)

b

b ∪ (ba∗a)

a ∪ (aa∗b)
∪ ((b ∪ (aa∗a))(b ∪ (ba∗a))∗(ε ∪ (ba∗b)))

20 / 23

From GNFA to Regular Expression

Complexity?

For FIT2004 students:
Compare this algorithm with the Floyd-Warshall algorithm for the All Pairs Shortest
Path problem.

21 / 23

Questions
I Can every language which is represented by a regular expression

be described by a finite automaton? YES

I Can every language which is described by a finite automaton
be represented by a regular expression? YES

I Can every language be represented by a regular expression or a finite automaton?

{ all languages } representable by
regexp

⇐⇒ recognised by
FA

?
22 / 23

Revision

Previous lecture:

I Understand Kleene’s Theorem

I Be able to convert Regular Expressions into NFA

I Be able to convert NFA into a Finite Automaton

Today:

I Be able to convert a FA into a Regular Expression

Reference
Sipser, Ch. 1, especially pp. 66, 69–76.

23 / 23