Transcript aug26
CS 44 – Aug. 26
• Finish section 1.1
– Definition of FA
– Examples
– Regular languages
– Union of 2 regular languages (handout)
Formal Definition
A finite automaton has 5 things:
1.
2.
3.
4.
5.
A set of states
An alphabet, for input
A start state
A set of accept states
Transition function: δ(state, input) = state
•
When we create/define an FA, must specify all
5 things. A drawing does a pretty good job.
Example
0
1
s1
s2
s3
0
1
0, 1
From state
Input 0
Input 1
s1
s2
s1
s2
s1
s3
s3
s3
s3
Let’s make FA’s
1.
2.
3.
4.
5.
L = bit strings that have exactly two 1’s
L = starts with 01
L = ends with 01
L = has an even number of 1’s
L = starts and ends with same symbol
*** Very good idea to give meaningful names to your
states.
Since L is a set… how would we create an FA for the
complement of L?
Regular Language
• A regular language is a set of strings accepted
by some FA.
• Examples
– Starting with 01; ending with 01, containing 01.
– Strings of length 2.
– {0, 11}
• Any finite set is regular. Infinite sets are more
interesting. Yet, # states always finite!
Operations on sets
• We can create new regular sets from existing
ones, rather than starting from scratch.
• Binary operations
– Union
– Intersection
• Unary operations
– Complement
– Star: This is the concatenation of 0 or more
elements.
For example, if A = {0, 11}, then A* is { ε, 0, 11, 00,
1111, 011, 110, …}
• “Closure property”: you always get a regular set
when you use the above operations.
Union
• Book shows construction (see handout)
• We want to union two languages A1 and A2: M1
accepts A1 and M2 accepts A2. The combined
machine is called M.
• M pretends it’s running M1 and M2 at same time!
δ((r1,r2),a) = (δ1(r1,a),δ2(r2,a))
• # states increases because it’s the Cartesian
product of M1 and M2’s states.
• Next section will show easier way to do union.
Wolf, Goat, Cabbage
• A man would like to cross a river with his wolf,
goat and head of cabbage.
• Can only ferry 1 of 3 items at a time. Plus:
– Leaving wolf & goat alone: wolf will eat goat.
– Leaving goat & cabbage alone: goat will eat
cabbage.
• Yes, we can solve this problem using an FA!
– Think about possible states and transitions.