Transcript Day05-DecisionProblems_DFSM - Rose

MA/CSSE 474
Theory of Computation
Decision Problems
DFSMs
Your Questions?
• Friday's class
• Reading Assignments
• HW1 solutions
• HW2 or HW3
• Anything else
Some "Canonical" Languages
from our textbook
•
•
•
•
•
•
AnBn = {anbn : n >= 0}
Bal = { strings of balanced parentheses}
WW = {ww : w  *}
PalEven {wwR : w  *}
AnBnCn = {anbncn : n >= 0}
HPALL = {<T> : T is a Turing machine that
eventually halts, no matter what input it is given}
• PRIMES = {w : w is the binary encoding of a
prime integer}
Decision Problems
Recap - Decision Problems
A decision problem is simply a problem for which the
answer is yes or no (True or False). A decision
procedure answers a decision problem.
Examples:
• Given an integer n, does n have a pair of consecutive
integers as factors?
• The language recognition problem: Given a
language L and a string w, is w in L?
Our focus in this course
Recap - The Power of Encoding
Anything can be encoded as a string.
For example, on a computer everything is
encoded as a string of bits. Assume that we
have a scheme for encoding objects (integers,
for example).
<X> is the string encoding of X.
<X, Y> is the string encoding of the pair X, Y.
Problems that don’t look like decision problems
about strings and languages can be recast into
new problems that do look like that.
Web Pattern Matching
Pattern matching on the web:
• Problem: Given a search string w and a web
document d, do they “match”? In other words,
should a search engine, on input w, consider
returning d?
• An instance of the problem: (w, d)
• The language to be decided:
{<w, d> : d is a candidate match for the string w}
The Halting Problem
Does a program always halt?
• Problem: Given a program p, written in some
some standard programming language L, is p
guaranteed to halt, no matter what input it is
given?
• An instance of the problem: Does Python
program "print(input())" always halt?
• The language to be decided:
HPALL = {pL : p halts on all inputs}
Primality Testing
• Problem: Given a nonnegative integer n, is it
prime?
• An instance of the problem: Is 9 prime?
• To encode the problem we need a way to encode
each instance: We encode each nonnegative
integer as a binary string.
• The language to be decided (2 ways to express it):
PRIMES = {w : w is the binary encoding of
a prime integer}. Equivalent:
PRIMES = {<n> : n is a prime integer}.
Graph Connectivity
• Problem: Given an undirected graph G, is it connected?
• An instance of the problem:
1
2
4
3
5
• Encoding of the problem: Let V be a set of binary numbers, one for
each vertex in G. Then we construct G as follows:
• Write |V| as a binary number,
The string below encodes
• Write a list of edges; each pair of binary a connected graph, but
110/1/10/1/100/10/101/10/11
numbers represents one edge.
Encodes a graph that is
• Separate all such binary numbers by “/”. not connected.
101/1/10/1/100/10/101/10/11
Can you see why?
• The language to be decided: CONNECTED = {w  {0, 1, /}* : w =
n1/n2/…ni, where each ni is a binary string and w encodes a
connected graph, as described above}.
Turning Problems into Language
Recognition Problems
Cast multiplication as language recognition:
• Problem: Given two nonnegative integers,
compute their product.
• Encoding of the problem: Transform computing into
verification.
• The language to be decided:
L = {w of the form:
<integer1>x<integer2>=<integer3>, where:
<integern> is any well-formed integer, and
integer3 = integer1  integer2}
12x9=108  L
12=12  L
12x8=108  L
Turning Problems Into Language
Recognition Problems
Cast sorting as language recognition decision problem:
• Problem: Given a list of integers, sort it.
• Encoding of the problem: Transform the sorting
problem into one of examining a pair of lists.
• The language to be decided:
L = {w1 # w2: n1
(w1 is of the form <int1, int2, … intn>,
w2 is of the form <int1, int2, … intn>, and
w2 contains the same objects as w1 and
w2 is sorted)}
Examples:
<1,5,3,9,6>#<1,3,5,6,9>  L
<1,5,3,9,6>#<1,2,3,4,5,6,7>  L
The Traditional Problems and their
Language Formulations are Equivalent
By equivalent we mean that either problem can be
reduced to the other.
If we have a machine to solve either problem, we can
use it to build a machine to solve the other, using only
the starting machine and other functions that can be built
using machines of equal or lesser power.
We will see that eduction does not always preserve
efficiency!
An Example
Consider the multiplication example:
INTEGERPROD =
{w of the form
<integer1>x<integer2>=<integer3>, where:
<integern> is any well-formed integer representation, and
integer3 = integer1  integer2}
Given a multiplication procedure, we can build a language
recognition decision procedure :
Given the language recognition procedure, we can build a
multiplication procedure :
Regular Languages
Represents
Regular Expression
Regular
Language
Accepts
Finite State
Machine
A real-world FSM Example
A
C
B
D
Recap - Definition of a DFSM
M = (K, , , s, A), where:
K is a finite set of states
The D is for
Deterministic
 is a (finite) alphabet
s  K is the initial state (a.k.a. start state)
A  K is the set of accepting states
: (K  )  K is the transition function
Sometimes we will put an M subscript on K, , , s, or
A (for example, sM), to indicate that this component is
part of machine M.
Acceptance by a DFSM
Informally, M accepts a string w iff M winds up in some
element of A after it has finished reading w.
The language accepted by M, denoted L(M), is the
set of all strings accepted by M.
But we need more formal notations if we want to prove
things about machines and languages.
Configurations of a DFSM
A configuration of a DFSM M is an element of:
K  *
It captures the two things that affect M’s future
behavior:
• its current state
• the remaining input to be read.
The initial configuration of a DFSM M, on input w, is:
(sM, w)
Where sM is the start state of M.
The "Yields" Relations
The yields-in-one-step relation: |-M :
(q, w) ⊦M (q', w') iff
• w = a w' for some symbol a  , and
•  (q, a) = q'
The yields-in-zero-or-more-steps relation: ⊦M*
⊦M* is the reflexive, transitive closure of ⊦M .
Note that this accomplishes the same thing as the
"extended delta function" that we considered on
Day 1. Two notations for the same concept.
Computations Using FSMs
A computation by M is a finite sequence of
configurations C0, C1, …, Cn for some n  0
such that:
• C0 is an initial configuration,
• Cn is of the form (q, ),
for some state q  KM,
• i{0, 1, …, n-1} (Ci ⊦M Ci+1)
An Example Computation
A FSM M that accepts decimal representations of odd
integers:
even
odd
even
q0
q1
odd
On input 235, the configurations are:
(q0, 235)
⊦M
⊦M
⊦M
(q0, 35)
(q1, 5)
(q1, )
Thus (q0, 235) ⊦M * (q1, )
Accepting and Rejecting
A DFSM M accepts a string w iff:
(sM, w) ⊦M* (q, ), for some q  AM
A DFSM M rejects a string w iff:
(sM, w) ⊦M* (q, ), for some q  AM
The language accepted by M, denoted L(M), is the
set of all strings accepted by M.
Theorem: Every DFSM M, in configuration (q, w),
halts after |w| steps.
Thus a DFSM accepts or rejects every string.
Regular Languages
Definition:
A language L is regular
iff
L = L(M) for some DFSM M.
Example
L = {w  {a, b}* :
every a is immediately followed by a b}.
 can also be
represented as a
transition table:
q2 is a dead state.
state 
input 
a
b
q0
q1
q0
q1
q2
q0
q2
q2
q2
Exercises: Construct DFSMs for
L = {w  {0, 1}* : w has odd parity}.
iI.e. an odd number of 1's.
L = {w  {a, b}* :
no two consecutive characters are the same}.
L = {w  {a, b}* : #a(w) >= #b(w) }
L = {w  {a, b}* : ∀x,y{a, b}* (w=xy → | #a(x) - #b(x)| <= 2 ) }