Xem mẫu
- Lecture # 5
Theory Of Automata
By
Dr. MM Alam
- Lecture#4 Recap
•
Recursive way of defining languages
•
Recursive way examples
•
Regular expressions
•
Regular expression examples
- •
Construct a regular expression for all
words that contain exactly two b’s or
exactly three b’s, not more.
a*ba*ba* + a*ba*ba*ba* or
a*(b + Λ)a*ba*ba*
- Construct a regular expression for:
(i) all strings that end in a double letter.
(ii) all strings that do not end in a double
letter
(i)
(a + b)*(aa + bb)
(ii)
- •
Construct a regular expression for all
strings that have exactly one double letter
in them
•
(b + Λ)(ab)*aa(ba)*(b + Λ) + (a + Λ)
(ba)*bb(ab)*(a + Λ)
- Construct a regular expression for all strings
in which the letter b is never tripled. This
means that no word contains the substring
bbb
(Λ + b + bb)(a + ab + abb)*
Words can be empty and start and end with
a or b. A compulsory ‘a’ is inserted between
all repetitions of b’s.
- •
Construct a regular expression for all
words in which a is tripled or b is tripled,
but not both. This means each word
contains the substring aaa or the substring
bbb but not both.
(Λ + b + bb)(a + ab + abb)*aaa(Λ + b + bb)(a
+ ab + abb)* +
(Λ + a + aa)(b + ba + baa)*bbb(Λ + a + aa)(b
+ ba + baa)*
- •
Let r1, r2, and r3 be three regular
expressions. Show that the language
associated with (r1 + r2)r3 is the same as
the language associated with r1r3 + r2r3.
Show that r1(r2 + r3) is equivalent to r1r2
+ r1r3. This will be the same as providing
a ‘distributive law’ for regular expressions.
- (r1+ r2)r3:
The first expression can be either r1 or r2.
The second expression is always r3.
There are two possibilities for this language:
r1r3 or r2r3.
r1(r2 + r3):
The first expression is always r1.
It is followed by either r2 or r3.
- Question
•
Can a language be expressed by more
than one regular expressions, while given
that a unique language is generated by
that regular expression?
- Deterministic Finite Automata
•
Also known as Finite state machine, Finite
state automata
•
It represents an abstract machine which is
used to represent a regular language
•
A regular expression can also be
represented using Finite Automata
•
There are two ways to specify an FA:
Transition Tables and Directed Graphs.
- Graph Representation
– Each node (or vertex) represents a state, and
the edges (or arcs) connecting the nodes
represent the corresponding transitions.
– Each state can be labeled.
- Finite Automata
state
a, a, a,
0 1 2 3 ∑ = { a, b }
b b b
final state
start state transition
Input
•
Table
State a b
Representation
(continued) 0 1 1
–
An FSA may also be 1 2 2
represented with a 2 3 3
state-transition table.
The table for the
- Finite Automata Definition
•
An FA is defined as follows:-
– Finite no of states in which one state must be
initial state and more than one or may be
none can be the final states.
– Sigma Σ provides the input letters from which
input strings can be formed.
– FA Distinguishing Rule: For each state,
there must be an out going transition for each
input letter in Sigma Σ.
- •
Σ = {a,b} and states = 0,1,2 where 0 is an
initial state and 1 is the final state.
•
Transitions:
1. At state 0 reading a,b go to state 1,
2. At state 1 reading a, b go to state 2
3. At state 2 reading a, b go to state 2
- Transition Table Representation
Old state Input Next State
0 a 1
0 B 1
1 a 2
1 b 2
2 a 2
2 b 2
- Another way of representation…
Old States New States
Reading a Reading b
0 1 1
1 2 2
2 + 2 2
- FA directed graph
a,b
0-
a,b 1 a,b 2+
- Example
•
Σ = {a,b} and states = 0,1,2 where 0 is an
initial state and 1 is the final state.
•
Transitions:
1. At state 0 reading a go to state 1,
2. At state 0 reading b go to state 2,
3. At state 1 reading a,b go to state 2
4. At state 2 reading a, b go to state 2
- Transition Table Representation
Old state Input Next State
0 a 1
0 b 2
1 a 2
1 b 2
2 a 2
2 b 2
nguon tai.lieu . vn
