代写 algorithm parallel network theory EECS2001:

EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
amahmoodi@cse.yorku.ca
Office: Lassonde 2015 Course page: Moodle
Notes based on work by Professor Suprakash Datta
5/14/2019 EECS2001, Summer 2019 1

Finite Automata (Ch. 1)
• What is a computer?
• Real computers are too complicated
• Instead we use a computational model
• There are different computational models
• The simplest one is finite state machine or finite automata
• Finite automata: good models for computers with extremely limited memory
5/14/2019 EECS2001, Summer 2019 2

Finite Automata (Continued)
• It turns out that we can do many useful things with such a small memory
• We do interact with such computers on daily basis:
– Controller of an automatic door (two state “open” and “closed”)
– Controller of an elevator (only remembers current floor, direction of motion, and requests to be done
5/14/2019 EECS2001, Summer 2019 3

Finite Automata
We will :
• Design automata for simple problems
• Study languages recognized by finite automata.
•We start by Deterministic Finite Automata (DFA)
•They can recognize both finite and infinite languages
5/14/2019 EECS2001, Summer 2019 4

Finite Automata
The simplest machine that can recognize an infinite language.
“Read once”, “no write” procedure.
Useful for describing algorithms also. Used a lot in network protocol description.
5/14/2019 EECS2001, Summer 2019 5

A Simple Automaton (0)
transition states rules
01 10
q1 q2 q3
starting state
0,1
accepting state
5/14/2019 EECS2001, Summer 2019 6

start
A Simple Automaton (1)
01 10
q1 q2 q3 0,1
accept
on input “0110”, the machine goes:
q1 → q1 → q2 → q2 → q3 = “reject” 5/14/2019 EECS2001, Summer 2019
7

A Simple Automaton (2)
01 10
q1 q2 q3 0,1
on input “101”, the machine goes:
q1 → q2 → q3 → q2 = “accept”
5/14/2019 EECS2001, Summer 2019 8

A Simple Automaton (3)
01 10
q1 q2 q3
0,1
010: reject
11: accept 010100100100100: accept 010000010010: reject
: reject
5/14/2019 EECS2001, Summer 2019 9

Examples of languages accepted by DFA
• L = { w | w ends with 1}
• L = { w | w contains sub-string 00}
• L = { w | |w| is divisible by 3}
• L = { w | |w| is odd or w ends with 1}
• L = { w | |w| is divisible by 106}
Note:  = {0,1} in each case
5/14/2019 EECS2001, Summer 2019 10

DFA : Formal definition
• A deterministic finite automaton (DFA) M is defined by a 5-tuple M=(Q,,,q0,F)
– Q: finite set of states
– : finite alphabet
– : transition function :Q→Q – q0Q: start state
– FQ: set of accepting states
5/14/2019 EECS2001, Summer 2019 11

states Q = {q1,q2,q3} alphabet  = {0,1} start state q1
accept states F={q2} transition function :
01 10
q1 q2 q3
0,1
01
qqq 112
q2 q3 q2
q3 q2 q2
M = (Q,,,q,F)
5/14/2019 EECS2001, Summer 2019
12

Recognizing Languages (defn)
A finite automaton M = (Q,,,q,F) accepts a string/word w = w1…wn if and only if there is a sequence r0…rn of states in Q such that:
1) r0 = q0
2) (ri,wi+1) = ri+1 for all i = 0,…,n–1
3) rn  F
5/14/2019 EECS2001, Summer 2019 13

Regular Languages
The language recognized by a finite automaton M is denoted by L(M).
A regular language is a language for which there exists a recognizing finite automaton.
5/14/2019 EECS2001, Summer 2019 14

Example
• Let M be the machine
01 10
q1 q2 q3 0,1
• Let 𝐴 = 𝑤 𝑤 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠′𝑎𝑡 𝑙𝑒𝑎𝑠𝑡 𝑜𝑛𝑒 1 𝑎𝑛𝑑 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 0 𝑠 𝑓𝑜𝑙𝑙𝑜𝑤 𝑡h𝑒 𝑙𝑎𝑠𝑡 1}
The L(M) = A or M recognizes A
5/14/2019 EECS2001, Summer 2019 15

Example 1.7
Give formal description of finite automaton 𝑀 :
•𝑀= 𝑞,𝑞,0,1,𝛿,𝑞,𝑞 21212
• 𝛿 𝑖𝑠 𝑔𝑖𝑣𝑒𝑛 𝑏𝑦
• What is 𝐿 𝑀 ? 2
𝑤 𝑤𝑒𝑛𝑑𝑠𝑖𝑛1}
2
5/14/2019 EECS2001, Summer 2019 16

Example 1.9
Give formal description of finite automaton 𝑀 :
•𝑀= 𝑞,𝑞,0,1,𝛿,𝑞,𝑞 21211
• 𝛿 𝑖𝑠 𝑔𝑖𝑣𝑒𝑛 𝑏𝑦
{𝑞,0,𝑞 , 𝑞,1,𝑞 , 𝑞,0,𝑞 , 𝑞,1,q } 11122122
• What is 𝐿 𝑀 ? 2
𝑤 𝑤𝑖𝑠ε𝑜𝑟𝑒𝑛𝑑𝑠𝑖𝑛0}
3
5/14/2019 EECS2001, Summer 2019 17

Example 1.11
Give formal description of finite
automaton 𝑀 : 4
5/14/2019
EECS2001, Summer 2019 18

Example 1.11
•𝑀 = 𝑠,𝑞,𝑞,𝑟,𝑟 , 𝑎,𝑏,𝛿,𝑠, 𝑞,𝑟 4 1212 11
• Define 𝛿 𝑢𝑠𝑖𝑛𝑔 𝑎 𝑡𝑎𝑏𝑙𝑒
• 𝐿 𝑀 = 𝑤 𝑤𝑠𝑡𝑎𝑟𝑡𝑠𝑎𝑛𝑑𝑒𝑛𝑑𝑠𝑤𝑖𝑡h 𝑎
4 𝑜𝑟 𝑠𝑡𝑎𝑟𝑡𝑠 𝑎𝑛𝑑 𝑒𝑛𝑑𝑠 𝑤𝑖𝑡h 𝑏}
5/14/2019 EECS2001, Summer 2019 19

Design DFA
• Given a language, you are asked to design a finite automaton that recognizes it
• Use “reader as automaton” method: put yourself in place of the machine
• What would you do?
• Where am in the string? Where does it end?
• You need to know what to remember 5/14/2019 EECS2001, Summer 2019 20

Example
• Suppose Σ = 0,1 𝑎𝑛𝑑
• 𝐿= 𝑤 𝑤h𝑎𝑠𝑎𝑛𝑜𝑑𝑑𝑛𝑢𝑚𝑏𝑒𝑟𝑜𝑓1𝑠}
• Construct a finite automaton that recognizes L
• You do not need to remember the entire string.
• Just need to remember if the number of 1s read so far is even or odd.
5/14/2019 EECS2001, Summer 2019 21

Example (Continued)
• Need only two states
• Now you need to know when to switch state and start and accepting state
5/14/2019 EECS2001, Summer 2019 22

DFA design (example)
• Design DFA for language
– L = {w  {0,1}* | w contains substring 01}
• What are the states to remember?
– Have seen the substring 01
– Not seen substring 01 and last symbol was 0
– Not seen substring 01 and last symbol was not 0
5/14/2019 EECS2001, Summer 2019 23

Two DFA Questions
Given the description of a finite automaton M = (Q,,,q,F), what is the language L(M) that it recognizes?
In general, what kind of languages can be recognized by finite automata? (What are the regular languages?)
5/14/2019 EECS2001, Summer 2019 24

Union of Two Languages
Theorem 1.12: If A1 and A2 are regular languages, then so is A1  A2.
(The regular languages are ‘closed’ under the union operation.)
Proof idea: A1 and A2 are regular, hence there are two DFA M1 and M2, with A1=L(M1) and A2=L(M2). Out of these two DFA, we will make a third automaton M3 such that L(M3) = A1  A2.
5/14/2019 EECS2001, Summer 2019 25

Proof Union-Theorem (1)
M1=(Q1,,1,q1,F1) and M2=(Q2,,2,q2,F2) Define M3 = (Q3,,3,q3,F3) by:
• Q3 = Q1Q2 = {(r1,r2) | r1Q1 and r2Q2} • 3((r1,r2),a) = (1(r1,a), 2(r2,a))
• q3 = (q1,q2)
• F3 = {(r1,r2) | r1F1 or r2F2}
5/14/2019 EECS2001, Summer 2019 26

Proof Union-Theorem (2)
The automaton M3 = (Q3,,3,q3,F3) runs M1 and M2 in ‘parallel’ on a string w.
In the end, the final state (r1,r2) ‘knows’
if wL1 (via r1F1?) and if wL2 (via r2F2?)
The accepting states F3 of M3 are such that wL(M3) if and only if wL1 or wL2, for: F3 = {(r1,r2) | r1F1 or r2F2}.
5/14/2019 EECS2001, Summer 2019 27

Concatenation of L1 and L2
Definition: L1• L2 = { xy | xL1 and yL2 } Example: {a,b} • {0,11} = {a0,a11,b0,b11}
Theorem 1.13: If L1 and L2 are regular langues, then so is L1•L2.
(The regular languages are ‘closed’ under concatenation.)
5/14/2019 EECS2001, Summer 2019 28

Proving Concatenation Thm.
Consider the concatenation: {1,01,11,001,011,…} • {0,000,00000,…} (That is: the bit strings that end with a “1”, followed by an odd number of 0’s.)
Problem is: given a string w, how does the automaton know where the L1 part stops and the L2 substring starts?
We need an M with ‘lucky guesses’. 5/14/2019 EECS2001, Summer 2019 29

Nondeterminism
Nondeterministic machines are capable of being lucky, no matter how small the probability.
A nondeterministic finite automaton has transition rules/possibilities like

1
q2
q1 q2 q11q3 5/14/2019 EECS2001, Summer 2019 30

A Nondeterministic Automaton
0,1
q1 q2 q3 q4
This automaton accepts “0110”, because there is a possible path that leads to an accepting state, namely:
q1 →q1 →q2 →q3 →q4→q4
5/14/2019 EECS2001, Summer 2019 31
0,1
1 0, 1

A Nondeterministic Automaton
0,1
q1 q2 q3 q4
The string 1 gets rejected: on “1” the automaton can only reach: {q1,q2,q3}.
0,1
1 0, 1
5/14/2019 EECS2001, Summer 2019 32

Nondeterminism ~ Parallelism
For any (sub)string w, the nondeterministic automaton can be in a set of possible states.
If the final set contains an accepting state, then the automaton accepts the string.
“The automaton processes the input in a
parallel fashion. Its computational path
is no longer a line, but a tree.” (Fig. 1.16)
5/14/2019 EECS2001, Summer 2019 33

Nondeterministic FA (def.)
• A nondeterministic finite automaton (NFA) M is defined by a 5-tuple M=(Q,,,q0,F), with
– Q: finite set of states
– : finite alphabet
– : transition function :Q→P (Q) – q0Q: start state
– FQ: set of accepting states
5/14/2019 EECS2001, Summer 2019 34

Nondeterministic :Q→P (Q) The function :Q→P (Q) is the crucial
difference. It means:
“When reading symbol “a” while in state q, one can go to one of the states in (q,a)Q.”
The  in  = {} takes care of the empty string transitions.
5/14/2019 EECS2001, Summer 2019 35

Recognizing Languages (def)
A nondeterministic FA M = (Q,,,q,F) accepts a string w = w1…wn if and only if we can rewrite w as y1…ym with yi and there is a sequence r0…rm of states in Q such that:
1) r0=q0
2) ri+1  (ri,yi+1) for all i=0,…,m–1
3) rm  F
5/14/2019 EECS2001, Summer 2019 36

Exercises
[Sipser 1.5]: Give NFAs with the specified number of states that recognize the following languages over the alphabet ={0,1}:
1. { w | w ends with 00}, three states
2. {0}; two states
3. { w | w contains even number of 0s, or exactly
two 1s}, six states
4. {0n | nN }, one state
5/14/2019 EECS2001, Summer 2019 37

Exercises – 2
Proof the following result:
“If L1 and L2 are regular languages, then
is a regular language too.”
L1 L2
Describe the language that is recognized
by this nondeterministic automaton:
1
0,1
1 0, 1
q1 q2 q3q4
5/14/2019 EECS2001, Summer 2019 38