Computer Language
Chapter 1: Regular Languages Last updated 2/26/21
Chapter 1.1: Finite Automata
Copyright By PowCoder代写 加微信 powcoder
What is a Computer?
Not a simple question to answer precisely
Computers are quite complicated
We start with a computational model
Different models will have different features and may match a real computer better in some ways and worse in others
Our first model is the finite state machine or finite automata
Finite Automata
Models of computers with extremely limited memory
Many simple computers have extremely limited memories and are in fact finite state machines
Can you name any? Hint: several are in this building but have nothing specifically to do with our department
Vending machine
Thermostat
Automatic door at supermarket
Automatic Door
What is the desired behavior? Describe the actions and then list the states.
Person approaches, door should open
Door should stay open while person going thru Door should shut if no one near doorway States are open and closed
More details about automatic door
Front pad Door Rear Pad Describe behavior now
Hint: action depends not just on what happens, but what state you are currently in
If you walk thru door should stay open when you are on rear pad
But if door is closed and someone steps on rear pad, door does not open
Automatic Door cont.
REAR, BOTH, FRONT, REAR, NEITHER BOTH
Closed NEITHER Open
More on Finite Automata
How many bits of data does this FSM store?
1 bit: open or closed
What about state information for elevators,
thermostats, vending machines,
FSM used in speech processing, optical character recognition, etc.
Have you implemented FSM? What?
I have implemented network protocols and expert systems for diagnosing telecommunication equipment problems
A finite automata M1
A finite automata M1 with 3 states
We see the state diagram
Start state q1, accept state q2 (double circle), and several transitions
If a string like 1101 will accept if ends in accept state or else reject. What will it do?
Can you describe all string that this model will accept?
It will accept all strings ending in a 1 and any string with an even number of 0’s following the last 1
Formal Definition of Finite Automata
A finite automata is a 5
Q is a finite set called states
is a finite set called the alphabet
Q is the transition function Q is the start state
Q is the set of accept states
Describe M1 using Formal Definition
q1 is the start state
{q1, q2, q3} {0,1}
Transition function
The Language of M1
If A is the set of all strings that a machine M accepts, then A is the language of M
We also say that M recognizes A or M accepts A
A machine may accept many strings, but only one language
Convention: M accepts string and recognizes a language
What is the Language of M1?
L(M1) = A or M1 recognizes A What is A?
A = {w | …….}
A = {w| w contains at least one 1 and an even number of 0’s follows the last 1}
What is the Language of M2?
M2 = {{q1,q2}, {0,1},
, q1, {q2}} as an exercise
L(M2) = {w| ? }
L(M2) = {w| w ends in a 1}
What is the language of M2?
What is the Language of M3?
M3 is M2 with different accept state What is the language of M3?
L(M3) = {w| ? }
L(M3) = {w| w ends in 0} [Not quite right! Why?]
L(M3) = {w| w is the empty string
or ends in 0}
What is the Language of M4?
M4 is a 5 state automata (Figure 1.12 on page 38)
What language does M4 accept?
What is the Language of M4?
What does M4 accept?
All strings that start and end with a or start and end with b
More simply, language is all string starting and ending with the same symbol
Note that length of 1 is okay
Construct M5 to do Modulo Arithmetic
Construct M5 to accept a string only if the sum of each input symbol is a multiple of 3 and RESET sets the sum back to 0 (1.13, page 39)
= {RESET, 0, 1, 2}
2,
11 1,
0,
Now Generalize M5
Generalize M5 to accept if sum of symbols is a multiple of
How many states are needed? What is the start and accept state?
instead of 3 (with same
({q0, q1, q2, q3, …, q
{0,1,2,RESET},
is finite, we are okay and only need finite
, RESET) = j
where k=j+1 modulo where k=j+2 modulo
Note: as long as memory (# of states)
Could you generalize on
1, 2, 3, …k}?
Formal Definition of Accept
Definition of M accepting a string:
Let M = (Q,
, q0, F) be a finite automata and let
be a string where
. Then M accepts w if a sequence of states r
in Q exists with 3 conditions
=0, 1, …, n
, end in accept state, and input symbols yield 0
We start in q
path from start to accept that follows transition table
Regular Languages
Definition: A language is called a regular language if some finite automata recognizes it
That is, all strings in a regular language are accepted by some finite automata
Why should you expect proofs by construction coming up in your next homework?
Designing Finite Automata
You will need to design FA’s to accept a language Strategies
Determine what you need to remember (the states)
E.g., how many states to determine even vs. odd number of 1’s?
What does each state represent? Use
meaningful state labels
Set the start and finish states based on what each state represents
Assign the transitions
Check solution: should accept w Be careful about the empty string!
L and not accept w
FA Design Example 1
Design a FA to accept the language of binary
strings where the number of 1’s is odd
FA Design Example 2
Design a FA to accept all string with 001 as a substring (page 44).
Regular Operations
Let A and B be languages. We define 3 regular operations:
Union: A Concatenation: A
Star is a unary operator on a single language
Star repeats a string 0 or more times
Star: A* = {x
| k ≥ 0 and each x
Examples of Regular Operations
Let A = {good, bad} and B = {boy, girl} Then what is:
A* = { badgood
B = {good, bad, boy, girl}
goodboy A*
goodgirl goodgood
, , good, bad,
goodbad , …}
goodgoodgood
The natural numbers is closed under addition and multiplication (but not division and subtraction)
A collection of objects is closed under an operation if applying that operation to members of the collection returns an object in the collection
Closure for Regular Languages
Regular languages are closed under the 3 regular operators we just introduced
Can you look ahead to see why we care?
If these operators are closed, then if we can implement each operator using a FA, then we can build a FA to recognize a regular expression
Closure of Union
Theorem 1.25: The class of regular languages is closed under the union operation
We need to simulate M1 and M2 running in parallel and stop if either reaches an accept state
This last part is feasible since we can have multiple accept states You need to remember where you would be in both machines
How can we prove this? Use proof by construction.
are regular languages then so is A Assume M1 accepts A1 and M2 accepts A2
Construct M3 using M1 and M2 to accept
Closure of Union II
You need to generate a state to represent the state you would be in with M1 and M2
, Q={(r1,r2)|r1
) and M2=(
Let M1=(Q 1
Build M3 as follows (we will do Q,
, F, (Cartesian product)
is the pair (q
stays the same but could more generally be
Closure of Concatenation
Theorem 1.26: The class of regular languages is closed under the concatenation operator
Not trivial since cannot just concatenate M1 and M2, where start states of M2 become the finish states of M1
Because we do not accept a string as soon as it enters the finish state (wait until string is done) it can leave and come back
Thus we do not know when to start using M2; if we make the wrong choice will not accept a string that can be accepted
Example on next slides
This proof is easy if we have nondeterministic FA
If A1 and A2 are regular languages then so is A1 Can you see how to do this simply?
Concatenation Example that Works
First here is an example I think will work
L(M1) = A, where with exactly 2 1’s
= {0, 1} and
= {0, 1} and
A = binary string
L(M2) = B, where with exactly 3 1’s
B = binary string
M1 will enter accept state as soon as sees 2 1’s. It can then loop back on any 0’s or move to M2 without issue. It can move immediately to M2 on a 1, and not have an issue since it cannot loop back, since A accepts only exactly 2 1’s. Once in M2 everything will work okay.
Concatenation Example that Fails
◼ L(M1) = A, where
◼ L(M2) = B, where
◼ This does not work (but easy with NFA or more complicated DFA)
= {0, 1} and = {0, 1} and
A = binary string with
B = binary string with exactly 2 1’s
If in M1 and see 2 1’s, enter accept state. When see another 1, have choice to loop back into accept state in M1, or start moving into M2, to the state that represents saw first 1 for string in B.
If the concatenated string has exactly 4 1’s total, then will only accept if move into M2 as early as possible (after seeing the first 2 1’s)
If the concatenated string has more than 4 1’s, then will only accept if loop in M1 accept state until only 2 1’s left.
Note that the general procedure for putting M1 and M2 together involves superimposing the start state for M2 onto accept state of M1 and removing the original arcs in M1 for that state.
Chapter 1.2: Nondeterminism
Nondeterminism
So far our FA is deterministic in that the state and next symbol determines the next state
In a nondeterministic machine, several choices may exist
DFA’s have one transition arrow per alphabet symbol, while NFAs have 0 or more for each and ε
q 1 q 0,ε 1 q 1 2 q3 4
How does an NFA Compute?
When there is a choice, all paths are followed
Think of it as cloning a process and continuing
If there is no arrow, the path terminates and the clone dies (it does not accept if at an accept state when that happens)
An NFA may have the empty string cause a transition The NFA accepts if any path is in the accept state Can also be modeled as a tree of possibilities
An alternative way of thinking of this
At each choice you make one guess of which way to go You magically always guess the right way to go
Try Computing This!
q 1 q 0,ε 1 q 1 2 q3 4
Try out 010110
Is it accepted?
What is the language?
Strings containing a substring of 101 or 11
Construct an NFA
Construct an NFA that accepts all string over {0,1} with a 1 in the third position from the end
Hint: the NFA stays in the start state until it guesses that it is three places from the end
Construct an NFA
Construct an NFA that accepts all string over {0,1} with a 1 in the third position from the end
Hint: the NFA stays in the start state until it guesses that it is three places from the end
q 1 q 0, 1 0,1 q 1 2 q3 4
Can we generate a DFA for this?
Yes, but it is more complicated and has 8 states
See book Figure 1.32 page 51
Each state represents the last 3 symbols seen, where we assume we start with 000
So, states 000, 001, 010, 011, …, 111 What is the transition from 010
On a 1 we go to 101 On a 0 we go to 100
Formal Definition of Nondeterministic Finite Automata
Similar to DFA except
state is not a state but a set of possible states
is the transition function Q is the set of accept states
A nondeterministic finite automata is a 5
Q is a finite set called states
, F) where
is a finite set called the alphabet
Q is the start state
Example of Formal Definition of
q 1 q 0,ε 1 q 1 2 q3 4
is the start state
Equivalence of NFAs and DFAs
NFAs and DFAs recognize same class of languages What does this mean? What is the implication?
NFAs have no more power than DFAs
With respect to what can be expressed
Every NFA has an equivalent DFA
But NFAs may make it easier to describe some languages
Terminology: Two machines are equivalent if they recognize the same language
Similar Idea you are More Familiar with
C, C++, Python, Pascal, Fortran, … Are these languages equivalent?
Some are more suited to some tasks, but with enough effort any of these languages can compute anything the others can
If necessary, you can even write a compiler for one language using another
Proof of Equivalence of NFA & DFA
Proof idea
Need to simulate an NFA with a DFA
With NFA’s, given an input we follow all possible branches and keep a finger on the state for each
That is what we need to keep track of
the states we
would be in for each branch
If the NFA has k states then it has 2
possible subsets
Each subset corresponds to one of the possibilities that the DFA needs to remember
The DFA will have 2
Proof by Construction
Lets do the easy ones first (skip
Let N=(Q, Construct DFA M =
, F) be the NFA recognizing A
’ for now)
Transition function
change the proof
Q’| R contains an accept state of N} The state R in M corresponds to a set of states in N
When M reads symbol
in state R, it shows where
we just need to keep track of more states
takes each state
, but taking that into account does not fundamentally
) = Union of
Example: Convert an NFA to a DFA
See example 1.41
3 is included because if we start in 1 we can immediately move to 3 What are the accept states?
{{1}, {1,2}, {1,3}, {1,2,3}}
For now don’t look at solution DFA
The NFA has 3 states: Q = {1, 2, 3} What are the states in the DFA?
What are the start states of the DFA?
, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
Start states of NFA include those reachable by {1, 3}
Example: Convert an NFA to a DFA
Now let’s work on some of the transitions
Let’s look at state 2 in NFA and complete the transitions for state 2 in the DFA
Where do we go from state 2 on an “a” and “b”
On “a” to state 2 and 3 and on “b” to state 3
So, what state does {2} in DFA go to for a and b?
Answer: on a to {2,3} and {3} for b Now let’s do state {3}
On “a” goes to {1,3} and on b goes to
Why {1, 3}? Because first goes to 1 then
permits a move back to 3!
DFA equivalent to NFA on next slide (
and Fig. 1.43, pg. 58 2
Any questions? Could you do it on a HW, exam, or
DFAs Equivalent to 3
Represents “Dead State”
Clearly not reachable
Can be simplified to DFA below since some states not reachable from start state. On HW or exam I would want to see the unsimplified version (can also show simplified)
Closure under Regular Operations
We started this before and did it for Union only
Union much simpler using NFA
Concatenation and Star much easier using NFA
Since DFAs equivalent to NFAs, we can now just use NFAs
Fewer states to keep track of because we can act as if we always “guess” correctly
Why do we care about closure?
We need to look ahead
A regular language is what a DFA/NFA accepts We are now introducing regular operators and then
will generate regular expressions from them (Ch 1.3)
We will want to show that the language of regular expressions is equivalent to the language accepted by NFAs/DFAs (i.e., a regular language)
How do we show this?
Basic terms in regular expression can generated by a FA
We can implement each operator using a FA and the combination is still able to be represented using a FA
Closure Under Union
Given two regular languages A
recognized by two NFAs N
Start by writing down N 1
branches to the start states of N 1
Isn’t that easy!
N to recognize A
How do we construct N? Think!
, construct
. Now what? ε
Add a new start state and then have it take
Closure under Concatenation
Given two regular languages A
recognized by two NFAs N
, construct N
switch from handling A
The complication is that we did not know when to
to recognize A How do we do this?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com