CISC 603: Theory of Computation
CISC 603: Theory of Computation
Textbook
Primary – Linz 6e
Supplemental – Rosen 7e
What does this course cover?
Computational Theory
In theoretical computer science, the theory of computation is the sub-discipline that focuses on how efficiently problems can be solved on a model of computation (mathematical abstraction of a computer).
The field is divided into three major branches:
automata theory and languages
computability theory
computational complexity theory
They try to answer the question:
“What are the fundamental capabilities and
limitations of computers?“
Why is this important?
Automata Theory
Automata theory is the study of abstract computational devices. Abstract devices are (simplified) models of real computations.
Computations happen everywhere: On your laptop, on your cell phone, in your mind…
Source: https://web2.qatar.cmu.edu/~dabousen/theory%20of%20computation.html
Computability Theory
Computability theory deals primarily with the question of the extent to which a problem is solvable on a computer.
The statement that the halting problem cannot be solved by a Turing machine is one of the most important results in computability theory, as it is an example of a concrete problem that is both easy to formulate and impossible to solve using a Turing machine.
Much of computability theory builds on the halting problem result.
Source: https://web2.qatar.cmu.edu/~dabousen/theory%20of%20computation.html
Complexity Theory
Complexity theory considers not only whether a problem can be solved at all on a computer, but also how efficiently the problem can be solved. Two major aspects are considered:
Time complexity: how many steps does it take to perform a computation
Space complexity: how much memory is required to perform that computation.
Source: https://web2.qatar.cmu.edu/~dabousen/theory%20of%20computation.html
Why should we study computational theory?
Deeper understanding
To put the Science in Computer Science
Philosophical implications
Understanding the mathematical laws that govern efficient computation
Bridging the gap between mathematics and computer science.
Research Areas:
Design and Analysis of Algorithms
Computational Complexity
Logic in Computer Science
Error-Correcting Codes
Cryptography
Randomness in Computation
Quantum Computation
Basic Structures: Sets, Functions, Sequences, Sums, and Matrices
Chapter 2
Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Sets
Section 2.1
Section Summary
Definition of sets
Describing Sets
Roster Method
Set-Builder Notation
Some Important Sets in Mathematics
Empty Set and Universal Set
Subsets and Set Equality
Cardinality of Sets
Tuples
Cartesian Product
Introduction
Sets are one of the basic building blocks for the types of objects considered in discrete mathematics.
Important for counting.
Programming languages have set operations.
Set theory is an important branch of mathematics.
Many different systems of axioms have been used to develop set theory.
Here we are not concerned with a formal set of axioms for set theory. Instead, we will use what is called naïve set theory.
Sets
A set is an unordered collection of objects.
the students in this class
the chairs in this room
The objects in a set are called the elements, or members of the set. A set is said to contain its elements.
The notation a ∈ A denotes that a is an element of the set A.
If a is not a member of A, write a ∉ A
Describing a Set: Roster Method
S = {a,b,c,d}
Order not important
S = {a,b,c,d} = {b,c,a,d}
Each distinct object is either a member or not; listing more than once does not change the set.
S = {a,b,c,d} = {a,b,c,b,c,d}
Elipses (…) may be used to describe a set without listing all of the members when the pattern is clear.
S = {a,b,c,d, ……,z }
Roster Method
Set of all vowels in the English alphabet:
V = {a,e,i,o,u}
Set of all odd positive integers less than 10:
O = {1,3,5,7,9}
Set of all positive integers less than 100:
S = {1,2,3,……..,99}
Set of all integers less than 0:
S = {…., -3,-2,-1}
Some Important Sets
N = natural numbers = {0,1,2,3….}
Z = integers = {…,-3,-2,-1,0,1,2,3,…}
Z⁺ = positive integers = {1,2,3,…..}
R = set of real numbers
R+ = set of positive real numbers
C = set of complex numbers.
Q = set of rational numbers
Some important symbols
GO TO PDF!
Set-Builder Notation
Specify the property or properties that all members must satisfy:
S = {x | x is a positive integer less than 100}
O = {x | x is an odd positive integer less than 10}
O = {x ∈ Z⁺ | x is odd and x < 10}
A predicate may be used:
S = {x | P(x)}
Example: S = {x | Prime(x)}
Positive rational numbers:
Q+ = {x ∈ R | x = p/q, for some positive integers p,q}
Interval Notation
[a,b] = {x | a ≤ x ≤ b}
[a,b) = {x | a ≤ x < b}
(a,b] = {x | a < x ≤ b}
(a,b) = {x | a < x < b}
closed interval [a,b]
open interval (a,b)
Universal Set and Empty Set
The universal set U is the set containing everything currently under consideration.
Sometimes implicit
Sometimes explicitly stated.
Contents depend on the context.
The empty set is the set with no
elements. Symbolized ∅, but
{} also used.
U
Venn Diagram
a e i
o u
V
John Venn (1834-1923)
Cambridge, UK
Some things to remember
Sets can be elements of sets.
{{1,2,3},a, {b,c}}
{N,Z,Q,R}
The empty set is different from a set containing the empty set.
∅ ≠ { ∅ }
Set Equality
Definition: Two sets are equal if and only if they have the same elements.
Therefore if A and B are sets, then A and B are equal if and only if .
We write A = B if A and B are equal sets.
{1,3,5} = {3, 5, 1}
{1,5,5,5,3,3,1} = {1,3,5}
22
Subsets
Definition: The set A is a subset of B, if and only if every element of A is also an element of B.
The notation A ⊆ B is used to indicate that A is a subset of the set B.
A ⊆ B holds if and only if is true.
Because a ∈ ∅ is always false, ∅ ⊆ S ,for every set S.
Because a ∈ S → a ∈ S, S ⊆ S, for every set S.
Showing a Set is or is not a Subset of Another Set
Showing that A is a Subset of B: To show that A ⊆ B, show that if x belongs to A, then x also belongs to B.
Showing that A is not a Subset of B: To show that A is not a subset of B, A ⊈ B, find an element x ∈ A with x ∉ B. (Such an x is a counterexample to the claim that x ∈ A implies x ∈ B.)
Examples:
The set of all computer science majors at your school is a subset of all students at your school.
The set of integers with squares less than 100 is not a subset of the set of nonnegative integers.
Another look at Equality of Sets
Recall that two sets A and B are equal, denoted by A = B, iff
Using logical equivalences we have that A = B iff
This is equivalent to
A ⊆ B and B ⊆ A
Proper Subsets
Definition: If A ⊆ B, but A ≠B, then we say A is a proper subset of B, denoted by A ⊂ B. If A ⊂ B, then
is true.
Venn Diagram
U
B
A
Set Cardinality
Definition: If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is finite. Otherwise it is infinite.
Definition: The cardinality of a finite set A, denoted by |A|, is the number of (distinct) elements of A.
Examples:
|ø| = 0
Let S be the letters of the English alphabet. Then |S| = 26
|{1,2,3}| = 3
|{ø}| = 1
The set of integers is infinite.
Power Sets
Definition: The set of all subsets of a set A, denoted P(A), is called the power set of A.
Example: If A = {a,b} then
P(A) = {ø, {a},{b},{a,b}}
Tuples
The ordered n-tuple (a1,a2,…..,an) is the ordered collection that has a1 as its first element and a2 as its second element and so on until an as its last element.
Two n-tuples are equal if and only if their corresponding elements are equal.
2-tuples are called ordered pairs.
The ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.
Set Operations
Section 2.2
Section Summary
Set Operations
Union
Intersection
Complementation
Difference
More on Set Cardinality
Set Identities
Proving Identities
Membership Tables
Boolean Algebra
Propositional calculus and set theory are both instances of an algebraic system called a Boolean Algebra. This is discussed in Chapter 12.
The operators in set theory are analogous to the corresponding operator in propositional calculus.
As always there must be a universal set U. All sets are assumed to be subsets of U.
Union
Definition: Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set:
Example: What is {1,2,3} ∪ {3, 4, 5}?
Solution: {1,2,3,4,5}
U
A
B
Venn Diagram for A ∪ B
Intersection
Definition: The intersection of sets A and B, denoted by A ∩ B, is
Note if the intersection is empty, then A and B are said to be disjoint.
Example: What is? {1,2,3} ∩ {3,4,5} ?
Solution: {3}
Example:What is?
{1,2,3} ∩ {4,5,6} ?
Solution: ∅
U
A
B
Venn Diagram for A ∩B
Complement
Definition: If A is a set, then the complement of the A (with respect to U), denoted by Ā is the set U - A
Ā = {x ∈ U | x ∉ A}
(The complement of A is sometimes denoted by Ac .)
Example: If U is the positive integers less than 100, what is the complement of {x | x > 70}
Solution: {x | x ≤ 70}
A
U
Venn Diagram for Complement
Ā
Difference
Definition: Let A and B be sets. The difference of A and B, denoted by A – B, is the set containing the elements of A that are not in B. The difference of A and B is also called the complement of B with respect to A.
A – B = {x | x ∈ A x ∉ B} = A ∩B
U
A
B
Venn Diagram for A − B
The Cardinality of the Union of Two Sets
Inclusion-Exclusion
|A ∪ B| = |A| + | B| − |A ∩ B|
Example: Let A be the math majors in your class and B be the CS majors. To count the number of students who are either math majors or CS majors, add the number of math majors and the number of CS majors, and subtract the number of joint CS/math majors.
We will return to this principle in Chapter 6 and Chapter 8 where we will derive a formula for the cardinality of the union of n sets, where n is a positive integer.
U
A
B
Venn Diagram for A, B, A ∩ B, A ∪ B
Set Identities
Identity laws
Domination laws
Idempotent laws
Complementation law
Continued on next slide
38
Set Identities
Commutative laws
Associative laws
Distributive laws
Continued on next slide
39
Set Identities
De Morgan’s laws
Absorption laws
Complement laws
40
Proving Set Identities
Different ways to prove set identities:
Prove that each set (side of the identity) is a subset of the other.
Use set builder notation and propositional logic.
Membership Tables: Verify that elements in the same combination of sets always either belong or do not belong to the same side of the identity. Use 1 to indicate it is in the set and a 0 to indicate that it is not.
Proof of Second De Morgan Law
Example: Prove that
Solution: We prove this identity by showing that:
1) and
2)
Continued on next slide
Proof of Second De Morgan Law
These steps show that:
Continued on next slide
Proof of Second De Morgan Law
These steps show that:
Set-Builder Notation: Second De Morgan Law
Functions
Section 2.3
Section Summary
Definition of a Function.
Domain, Codomain
Image, Preimage
Injection, Surjection, Bijection
Inverse Function
Function Composition
Graphing Functions
Floor, Ceiling, Factorial
Partial Functions (optional)
Functions
Definition: Let A and B be nonempty sets. A function f from A to B, denoted f: A → B is an assignment of each element of A to exactly one element of B. We write f(a) = b if b is the unique element of B assigned by the function f to the element a of A.
Functions are sometimes
called mappings or
transformations.
A
B
C
Students
Grades
D
F
Kathy Scott
Sandeep Patel
Carlota Rodriguez
Jalen Williams
Functions
A function f: A → B can also be defined as a subset of A×B (a relation). This subset is restricted to be a relation where no two elements of the relation have the same first element.
Specifically, a function f from A to B contains one, and only one ordered pair (a, b) for every element a∈ A.
and
Functions
Given a function f: A → B:
We say f maps A to B or
f is a mapping from A to B.
A is called the domain of f.
B is called the codomain of f.
If f(a) = b,
then b is called the image of a under f.
a is called the preimage of b.
The range of f is the set of all images of points in A under f. We denote it by f(A).
Two functions are equal when they have the same domain, the same codomain and map each element of the domain to the same element of the codomain.
Representing Functions
Functions may be specified in different ways:
An explicit statement of the assignment.
Students and grades example.
A formula.
f(x) = x + 1
A computer program.
A Java program that when given an integer n, produces the nth Fibonacci Number (covered in the next section and also inChapter 5).
Cardinality of Sets
Section 2.5
Section Summary
Cardinality
Countable Sets
Computability
Cardinality
Definition: The cardinality of a set A is equal to the cardinality of a set B, denoted
|A| = |B|,
if and only if there is a one-to-one correspondence (i.e., a bijection) from A to B.
If there is a one-to-one function (i.e., an injection) from A to B, the cardinality of A is less than or the same as the cardinality of B and we write |A| ≤ |B|.
When |A| ≤ |B| and A and B have different cardinality, we say that the cardinality of A is less than the cardinality of B and write |A| < |B|.
Cardinality
Definition: A set that is either finite or has the same cardinality as the set of positive integers (Z+) is called countable. A set that is not countable is uncountable.
The set of real numbers R is an uncountable set.
When an infinite set is countable (countably infinite) its cardinality is ℵ0 (where ℵ is aleph, the 1st letter of the Hebrew alphabet). We write |S| = ℵ0 and say that S has cardinality “aleph null.”
Chapter 1
INTRODUCTION TO THE THEORY OF COMPUTATION
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Define the three basic concepts in the theory of computation: automaton, formal language, and grammar.
Solve exercises using mathematical techniques and notation learned in previous courses.
Evaluate expressions involving operations on strings.
Evaluate expressions involving operations on languages.
Generate strings from simple grammars.
Construct grammars to generate simple languages.
Describe the essential components of an automaton.
Design grammars to describe simple programming constructs.
Theory of Computation
Basic Concepts
Automaton: a formal construct that accepts input, produces output, may have some temporary storage, and can make decisions
Formal Language: a set of sentences formed from a set of symbols according to formal rules
Grammar: a set of rules for generating the sentences in a formal language
In addition, the theory of computation is concerned with questions of computability (the types of problems computers can solve in principle) and complexity (the types of problems that can solved in practice).
Formal Languages
Basic Concepts
Alphabet: set of symbols, i.e. Σ = {a, b}
String: finite sequence of symbols from Σ, such as v = aba and w = abaaa
Empty string (λ)
Substring, prefix, suffix
Operations on strings:
Concatenation: vw = abaabaaa
Reverse: wR = aaaba
Repetition: v2 = abaaba and v0 = λ
Length of a string: |v| = 3 and |λ| = 0
Formal Languages
Definitions
Σ* = set of all strings formed by concatenating zero or more symbols in Σ
Σ+ = set of all non-empty strings formed by concatenating symbols in Σ
In other words, Σ+ = Σ* - { λ }
A formal language is any subset of Σ*
Examples: L1 = { anbn: n ≥ 0 } and L2 = { ab, aa }
A string in a language is also called a sentence of the language
Formal Languages
Set Operations
A language is a set. Therefore, set operations are defined as usual.
If L1 = { anbn: n ≥ 0 } and L2 = { ab, aa }
Union: L1 ᴜ L2 = { aa, λ, ab, aabb, aaabbb, … }
Intersection: L1 ∩ L2 = { ab }
Difference: L1 - L2 = { λ, aabb, aaabbb, … }
Complement: L2 = Σ* - { ab, aa }
Practice: Find L2 – L1
Formal Languages
Other Operations
New languages can be produced by reversing all strings in a language, concatenating strings from two languages, and concatenating strings from the same language.
If L1 = { anbn: n ≥ 0 } and L2 = { ab, aa }
Reverse: L2R = { ba, aa }
Concatenation: L1L2 = { ab, aa, abab, abaa, aabbab, aabbaa, … }
The concatenation L2L2 or L22 = { abab, abaa, aaab, aaaa }
Star-Closure: L2* = L20 ᴜ L21 ᴜ L22 ᴜ L23 ᴜ …
Positive Closure: L2+ = L21 ᴜ L22 ᴜ L23 ᴜ …
Grammars
Definition
Precise mechanism to describe the strings in a language
Def. 1.1: A grammar G consists of:
V: a finite set of variable or non-terminal symbols
T: a finite set of terminal symbols
S: a variable called the start symbol
P: a set of productions
Example 1.11:
V = { S }
T = { a, b }
P = { S aSb, S λ }
Grammars
Derivation of Strings
Beginning with the start symbol, strings are derived by repeatedly replacing variable symbols with the expression on the right-hand side of any applicable production
Any applicable production can be used, in arbitrary order, until the string contains no variable symbols.
Sample derivation using grammar in Example 1.11:
S aSb (applying first production)
aaSbb (applying first production)
aabb (applying second production)
The Language Generated by a Grammar
Def. 1.2: For a given grammar G, the language generated by G, L(G), is the set of all strings derived from the start symbol
To show a language L is generated by G:
Show every string in L can be generated by G
Show every string generated by L is in G
A given language can normally be generated by different grammars
Equivalence of Grammars
Two grammars are equivalent if they generate the same language
For convenience, productions with the same left-hand sides are written on the same line
Example 1.14:
V = { A, S }, T = { a, b }, and productions
S aAb | λ
A aAb | λ
The grammars in examples 1.11 and 1.14 can be shown to be equivalent
Automata
An automaton is an abstract model of a digital computer
An automaton consists of
An input mechanism
A control unit
Possibly, a storage mechanism
Possibly, an output mechanism
Control unit can be in any number of internal states, as determined by a next-state or transition function.
Diagram of a General Automaton
Application
Grammars for Programming Languages
The syntax of constructs in a programming language is commonly described with grammars
Assume that in a hypothetical programming language,
Identifiers consist of digits and the letters a, b, or c
Identifiers must begin with a letter
Productions for a sample grammar:
Chapter 2
FINITE AUTOMATA
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Describe the components of a deterministic finite accepter (dfa)
State whether an input string is accepted by a dfa
Describe the language accepted by a dfa
Construct a dfa to accept a specific language
Show that a particular language is regular
Describe the differences between deterministic and nondeterministic finite automata (nfa)
State whether an input string is accepted by a nfa
Construct a nfa to accept a specific language
Transform an arbitrary nfa to an equivalent dfa
Deterministic Finite Accepters
Def 2.1: A deterministic finite accepter is defined by
Q: a finite set of internal states
(sigma) Σ: a set of symbols called the input alphabet
(delta) δ: a transition function from Q X Σ to Q
q0: the initial state
F: a subset of Q representing the final states
Example 2.1: Consider the dfa
Q = { q0, q1, q2 } Σ = { 0, 1 } F = { q1 }
where the transition function is given by
δ(q0, 0) = q0 δ(q0, 1) = q1 δ(q1, 0) = q0
δ(q1, 1) = q2 δ(q2, 0) = q2 δ(q2, 1) = q1
Transition Graphs
A DFA can be visualized with a Transition Graph
The graph below represents the dfa in Example 2.1:
Processing Input with a DFA
A DFA starts by processing the leftmost input symbol with its control in state q0. The transition function determines the next state, based on current state and input symbol
The DFA continues processing input symbols until the end of the input string is reached
The input string is accepted if the automaton is in a final state after the last symbol is processed. Otherwise, the string is rejected.
For example, the dfa in example 2.1 accepts the string 111 but rejects the string 110
The Language Accepted by a DFA
For a given dfa, the extended transition function δ* accepts as input a dfa state and an input string. The value of the function is the state of the automaton after the string is processed.
Sample values of δ* for the dfa in example 2.1,
δ*(q0, 1001) = q1 δ*(q1, 000) = q0
The language accepted by a dfa M is the set of all strings accepted by M. More precisely, the set of all strings w such that δ*(q0, w) results in a final state.
A Sample Deterministic Finite Accepter
Example 2.3 shows a dfa to accept the set of all strings on { a, b } that start with the prefix ab.
Example
Construct DFA to accept 00(0+1)*
q0
q1
q2
0
0
1
Ǿ
1
0,1
0, 1
Regular Languages
Finite automata accept a family of languages collectively known as regular languages.
A language L is regular if and only if there is a DFA that accepts L. Therefore, to show that a language is regular, one must construct a DFA to accept it.
Practice: show that L = {(ab)na, n > 0} is regular.
Regular languages have wide applicability in problems that involve scanning input strings in search of specific patterns.
Nondeterministic Finite Accepters
An automaton is nondeterministic if it has a choice of actions for given conditions
Basic differences between deterministic and nondeterministic finite automata:
In an nfa, a (state, symbol) combination may lead to several states simultaneously
If a transition is labeled with the empty string as its input symbol, the nfa may change states without consuming input
an nfa may have undefined transitions
Nondeterministic FA Example 2.7
Example 2.7 shows a nondeterministic fa in which there are two transitions labeled a out of state q0
More precisely, δ(q0, a) = { q1, q4 }
Nondeterministic FA Example 2.8
Example 2.8 shows a nondeterministic fa which contains both a -transition as well as undefined transitions
More precisely, δ(q0, ) = { q2 } and δ(q2, 0) =
The Language Accepted by a Nondeterministic FA
For a given nfa, the value of the extended transition function δ*(qi, w) is the set of all possible states for the control unit after processing w, having started in qi
Sample values of δ* for the nfa in example 2.9:
δ*(q0, 10) = { q0, q2 } δ*(q0, 101) = { q1 }
A string w is accepted if δ*(q0, w) contains a final state. In the example above, 10 would be accepted but 101 would be rejected.
As is the case with dfa, the language accepted by a nondeterministic fa M is the set of all accepted strings. The machine in example 2.9 accepts L = { (10)n: n ≥ 0 }
Equivalence of Deterministic and Nondeterministic Finite Accepters
Does nondeterminism make it possible to accept languages that deterministic fa cannot recognize?
As it turns out, per Theorem 2.2: For any nondeterministic finite accepter, there is an equivalent deterministic finite accepter
Therefore, every language accepted by a nondeterministic finite accepter is regular
To prove theorem 2.2, a constructive proof is given. The algorithm outlines the steps to follow when building a dfa equivalent to a particular nfa
Procedure: nfa-to-dfa Conversion
Beginning with the start state, define input transitions for the dfa as follows:
If the nfa input transition leads to a single state, replicate for the dfa
If the nfa input transition leads to more than one state, create a new state in the dfa labeled { qi, …, qj }, where qi, …, qj are all the states the nfa transition can lead to.
If the nfa input transition is not defined, the corresponding dfa transition should lead to a trap state.
Repeat step 1 for all newly created dfa states, until no new states are created.
Any dfa state containing an nfa final state in its label should be labeled as final.
If the nfa accepts the empty string, label the start dfa state a final state.
nfa-to-dfa Conversion Example
When applying the conversion procedure to the nfa below, we note the following nfa transitions
δ(q0, 0) = { q0, q1 } δ(q0, 1) = { q1 }
δ(q1, 0) = { q2 } δ(q1, 1) = { q2 }
δ(q2, 0) = δ(q2, 1) = { q2 }
Definitely an NFA because
nfa-to-dfa Conversion Example (cont.)
We add transitions from q0 to states { q0, q1 } and { q1 }
Note that δ(q0, 0) δ(q1, 0) = { q0, q1, q2 } and
δ(q0, 1) δ(q1, 1) δ(q2, 1) = { q1, q2 }
So we add transitions to states { q0, q1, q2 } and { q1, q2 }
nfa-to-dfa Conversion Example (cont.)
Note that δ(q1, 0) δ(q2, 0) = { q2 } and
δ(q1, 1) δ(q2, 1) = { q2 }
So we add 0-1 transitions from { q1, q2 } to { q2 }
Similarly, we add 0-1 transitions from { q1 } to { q2 }
Since δ(q2, 1) = { q2 }, we add the corresponding transition
Since δ(q2, 0) is undefined, we add a trap state (labeled ) as well as the corresponding transitions.
nfa-to-dfa Conversion Example (cont.)
Since there are no dfa states with undefined transitions, the process stops. All states containing q1 in their label are designated as final states.
Chapter 3
REGULAR LANGUAGES AND REGULAR GRAMMARS
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Identify the language associated with a regular expression
Find a regular expression to describe a given language
Construct a nondeterministic finite automaton to accept the language denoted by a regular expression
Use generalized transition graphs to construct a regular expression that denotes the language accepted by a given finite automaton
Identify whether a particular grammar is regular
Construct regular grammars for simple languages
Construct a nfa that accepts the language generated by a regular grammar
Construct a regular grammar that generates the language accepted by a finite automaton
Regular Expressions
Regular Expressions provide a concise way to describe some languages
Regular Expressions are defined recursively. For any alphabet:
the empty set, the empty string, or any symbol from the alphabet are primitive regular expressions
the union (+), concatenation (), and star closure (*) of regular expressions is also a regular expression
any string resulting from a finite number of these operations on primitive regular expressions is also a regular expression
Languages Associated with Regular Expressions
A regular expression r denotes a language L(r)
Assuming that r1 and r2 are regular expressions:
The regular expression denotes the empty set
The regular expression denotes the set { }
For any a in the alphabet, the regular expression a denotes the set { a }
The regular expression r1 + r2 denotes L(r1) L(r2)
The regular expression r1 r2 denotes L(r1) L(r2)
The regular expression (r1) denotes L(r1)
The regular expression r1* denotes (L(r1))*
Determining the Language Denoted by a Regular Expression
By combining regular expressions using the given rules, arbitrarily complex expressions can be constructed
The concatenation symbol () is usually omitted
In applying operations, we observe the following precedence rules:
star closure precedes concatenation
concatenation precedes union
Parentheses are used to override the normal precedence of operators
Sample Regular Expressions and Associated Languages
Regular Expression Language
(ab)* { (ab)n, n ≥ 0 }
a + b { a, b }
(a + b)* { a, b }* (in other words, any string formed with a and b)
a(bb)* { a, abb, abbbb, abbbbbb, … }
a*(a + b) { a, aa, aaa, …, b, ab, aab, … } (Example 3.2)
(aa)*(bb)*b { b, aab, aaaab, …, bbb, aabbb, … } (Example 3.4)
(0 + 1)*00(0 + 1)* Binary strings containing at least one pair of consecutive zeros
Two regular expressions are equivalent if they denote the same language. Consider, for example, (a + b)* and (a*b*)*
Regular Expressions and Regular Languages
Theorem 3.1: For any regular expression r, there is a nondeterministic finite automaton that accepts the language denoted by r
Since nondeterministic and deterministic accepters are equivalent, regular expressions are associated precisely with regular languages
A constructive proof of theorem 3.1 provides a systematic procedure for constructing a nfa that accepts the language denoted by any regular expression
Construction of a nondeterministic fa to accept a language L(r)
We can construct simple automata that accept the languages associated with the empty set, the empty string, and any individual symbol.
Construction of a nondeterministic fa to accept a language L(r) (cont.)
Given schematic representations for automata designed to accept L(r1) and (r2), an automaton to accept L(r1 + r2) can be constructed as shown in Figure 3.3
Construction of a nondeterministic fa to accept a language L(r) (cont.)
Given schematic representations for automata designed to accept L(r1) and (r2), an automaton to accept L(r1r2) can be constructed as shown in Figure 3.4
Construction of a nondeterministic fa to accept a language L(r) (cont.)
Given a schematic representation for an automaton designed to accept L(r1), an automaton to accept L(r1*) can be constructed as shown in Figure 3.5
Example: Construction of a nfa to accept a language L(r)
Given the regular expression r = (a + bb)* (ba* + ), a nondeterministic fa to accept L(r) can be constructed systematically as shown in Figure 3.7
Regular Expressions for Regular Languages
Theorem 3.2: For every regular language, it is possible to construct a corresponding r.e.
The process can be illustrated with a generalized transition graph (GTG)
A GTG for L(a* + a*(a + b)c*) is shown below
Regular Grammars
In a right-linear grammar, at most one variable symbol appears on the right side of any production. If it occurs, it is the rightmost symbol.
In a left-linear grammar, at most one variable symbol appears on the right side of any production. If it occurs, it is the leftmost symbol.
A regular grammar is either right-linear or left-linear.
Example 3.13 presents a regular (right-linear) grammar:
V = { S }, T = { a, b }, and productions S abS | a
Right-Linear Grammars Generate Regular Languages
Per theorem 3.3, it is always possible to construct a nfa to accept the language generated by a regular grammar G:
Label the nfa start state with S and a final state Vf
For every variable symbol Vi in G, create a nfa state and label it Vi
For each production of the form A → aB , label a transition from state A to B with symbol a
For each production of the form A → a, label a transition from state A to Vf with symbol a (may have to add intermediate states for productions with more than one terminal on RHS)
Example: Construction of a nfa to accept a language L(G)
Given the regular grammar G with productions
V0 aV1
V1 abV0 | b
a nondeterministic fa to accept L(G) can be constructed systematically as shown in Figure 3.17
Right-Linear Grammars for Regular Languages
Per theorem 3.4, it is always possible to construct a regular grammar G to generate the language accepted by a dfa M:
Each state in the dfa corresponds to a variable symbol in G
For each dfa transition from state A to state B labeled with symbol a, there is a production of the form A → aB in G
For each final state Fi in the dfa, there is a corresponding production Fi → λ in G
Example: Construction of a regular grammar G to generate a language L(M)
Given the language L(aab*a), Figure 3.18 shows the transition function for a dfa that accepts the language and the productions for the corresponding regular grammar.
Equivalence of Regular Languages and Regular Grammars
Chapter 5
CONTEXT-FREE LANGUAGES
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Identify whether a particular grammar is context-free
Discuss the relationship between regular languages and context-free languages
Construct context-free grammars for simple languages
Produce leftmost and rightmost derivations of a string generated by a context-free grammar
Construct derivation trees for strings generated by a context-free grammar
Show that a context-free grammar is ambiguous
Rewrite a grammar to remove ambiguity
Context-Free Grammars
Many useful languages are not regular
Context-free grammars are very useful for the definition and processing of programming languages
A context-free grammar has no restrictions on the right side of its productions, while the left side must be a single variable.
A language is context-free if it is generated by a context-free grammar
Since regular grammars are context-free, the family of regular languages is a proper subset of the family of context-free languages
Context-Free Grammars
Context-Free Grammars
Formally, a context-free grammar is a collection of four objects:
A set of nonterminal symbols (also called variables),
A set of terminal symbols (the alphabet of the CFG)
A set of production rules stating how each nonterminal can be converted by a string of terminals and nonterminals, and
A start symbol (which must be a nonterminal) that begins the derivation.
Context-Free Languages (Example 5.1)
Consider the grammar
V = { S }, T = { a, b }, and productions
S aSa | bSb |
Sample derivations:
S aSa aaSaa aabSbaa aabbaa
S bSb baSab baab
The language generated by the grammar is
{ wwR: w { a, b }*}
(in other words, even-length palindromes in { a, b }*)
1 2 3
Context-Free Languages (Example 5.4)
Consider the grammar
V = { S }, T = { a, b }, and productions
S aSb | SS |
Sample derivations:
S aSb aaSbb aabb
S SS aSbS abS abaSb abab
The language generated by the grammar is
{ w { a, b }*: na(w) = nb(w) and na(v) ≥ nb(v) }
(where v is any prefix of w)
1 2 3
Leftmost and Rightmost Derivations
In a leftmost derivation, the leftmost variable in a sentential form is replaced at each step
In a rightmost derivation, the rightmost variable in a sentential form is replaced at each step
Consider the grammar from example 5.5:
V = { S, A, B }, T = { a, b }, and productions
S aAB
A bBb
B A |
The string abb has two distinct derivations:
Leftmost: S aAB abBbB abbB abb
Rightmost: S aAB aA abBb abb
1
2
3
1 2 3 3
1 3 2 3
Derivation Trees
In a derivation tree or parse tree,
the root is labeled S
internal nodes are labeled with a variable occurring on the left side of a production
the children of a node contain the symbols on the corresponding right side of a production
For example, given the production A abABc, Figure 5.1 shows the corresponding partial derivation tree
Derivation Trees (Cont.)
The yield of a derivation tree is the string of terminals produced by a leftmost depth-first traversal of the tree
For example, using the grammar from example 5.5, the derivation tree below yields the string abbbb
Sentential Forms and Derivation Trees
Theorem 5.1 states that, given a context-free grammar G, for every string w in L(G), there exists a derivation tree whose yield is w
The converse is also true: the yield of any derivation tree formed with productions from G is in L(G)
Derivation trees show which productions are used in obtaining a sentence, but do not give the order of their application
Parsing and Membership
The parsing problem: given a grammar G and a string w, find a sequence of derivations using the productions in G to produce w
Can be solved in an exhaustive, top-down, but not very efficient fashion
Theorem 5.2: Exhaustive parsing is guaranteed to yield all strings eventually, but may fail to stop for strings not in L(G), unless we restrict the productions in the grammar to avoid the forms A and A B
Parsing and Ambiguity
A grammar G is ambiguous if there is some string w in L(G) for which more than one derivation tree exists
The grammar with productions S aSb | SS | λ is ambiguous, since the string aabb has two derivation trees, as shown below
Ambiguity in Programming Languages
Consider the grammar below, designed to generate simple arithmetic expressions such as (a+b)*c and a*b+c
V = { E, I }, T = { a, b, c, +, *, (, ) }, and productions
E I
E E+E
E E*E
E (E)
I a | b | c
The grammar is ambiguous because strings such as a+b*c have more than one derivation tree, as shown in Figure 5.5
1
2 3
4
5
Derivation Trees from Ambiguous Grammar
2
1
5
3
1
5
1
5
1
5
1
5
1
5
3
2
Resolving Ambiguity
Ambiguity can often be removed by rewriting the grammar so that only one parsing is possible
Consider the grammar
V = { E, T, F, I }, T = { a, b, c, +, *, (, ) }, and productions
E T
T F
F I
E E+T
T T*F
F (E)
I a | b | c
As shown in Figure 5.6, only one derivation tree yields the string a+b*c
Old Grammar
1
2
3
4
5
6
7
Derivation Tree for a+b*c Using Unambiguous Grammar
Ambiguous Languages
For some languages, it is always possible to find an unambiguous grammar, as shown in the previous example
However, there are inherently ambiguous languages, for which every possible grammar is ambiguous
Consider the language { anbnbm } { anbmbm }, which is generated by the grammar
S S1 | S2
S1 S1c | A
A aAb |
S2 aS2 | B
B bBc |
The grammar above (and every other equivalent grammar) is ambiguous, because any string of the form anbnbm has two distinct derivations
Summary
Context-free grammars give a way to describe a class of formal languages (the context-free languages) that are strictly larger than the regular languages.
A parse tree shows how a string can be derived from a grammar.
A grammar is ambiguous if it can derive the same string multiple ways.
There is no algorithm for eliminating ambiguity; it must be done by hand.
Chapter 6
SIMPLIFICATION OF CONTEXT-FREE GRAMMARS AND NORMAL FORMS
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Simplify a context-free grammar by removing useless productions
Simplify a context-free grammar by removing -productions
Simplify a context-free grammar by removing unit-productions
Determine whether or not a context-free grammar is in Chomsky normal form
Transform a context-free grammar into an equivalent grammar in Chomsky normal form
Determine whether or not a context-free grammar is in Greibach normal form
Transform a context-free grammar into an equivalent grammar in Greibach normal form
Methods for Transforming Grammars
The definition of a context-free grammar imposes no restrictions on the right side of a production
In some cases, it is convenient to restrict the form of the right side of all productions
Simplifying a grammar involves eliminating certain types of productions while producing an equivalent grammar, but does not necessarily result in a reduction of the total number of productions
For simplicity, we focus on languages that do not include the empty string
A Useful Substitution Rule
Theorem 6.1 states that, If A and B are distinct variables, a production of the form A uBv can be replaced by a set of productions in which B is substituted by all strings B derives in one step.
Consider the grammar
V = { A, B }, T = { a, b, c }, and productions
A a | aaA | abBc
B abbA | b
We can replace A abBc with two productions that replace B (in red), obtaining an equivalent grammar with productions
A a | aaA | ababbAc | abbc
B abbA | b
Useless Productions
A variable is useful if it occurs in the derivation of at least one string in the language
Otherwise, the variable and any productions in which it appears is considered useless
A variable is useless if:
No terminal strings can be derived from the variable
The variable symbol cannot be reached from S
In the grammar below, B can never be reached from the start symbol S and is therefore considered useless
S A
A aA |
B bA
None of these productions contain variable B
Removing Useless Productions
It is always possible to remove useless productions from a context-free grammar:
Let V1 be the set of useful variables, initialized to empty
Add a variable A to V1 if there is a production of the form
A terminal symbols or variables in already V1
(Repeat until nothing else can be added to V1)
Eliminate any productions containing variables not in V1
Use a dependency graph to identify and eliminate variables that are unreachable from S
Application of the Procedure for Removing Useless Productions
Consider the grammar from example 6.3:
S aS | A | C
A a
B aa
C aCb
In step 2, variables A, B, and S are added to V1
Since C is useless, it is eliminated in step 3, resulting in the grammar with productions
S aS | A
A a
B aa
In step 4, B is identified as unreachable from S, resulting in the grammar with productions
S aS | A
A a
C will never produce a terminal!
-Productions
A production with on the right side is called a -production
A variable A is called nullable if there is a sequence of derivations through which A produces
If a grammar generates a language not containing , any -productions can be removed
In the grammar below, S1 is nullable
S aS1b
S1 aS1b|
Since the language is -free, we have the equivalent grammar
S aS1b | ab
S1 aS1b | ab
Removing -Productions
It is possible to remove -productions from a context-free grammar that does not generate :
Let VN be the set of nullable variables, initialized to empty
Add a variable A to VN if there is a production having one of the forms:
A λ
A variables already in VN
(Repeat until nothing else can be added to VN)
Eliminate -productions
Add productions in which nullable symbols are replaced by λ in all possible combinations
Application of the Procedure for Removing -Productions
Consider the grammar from example 6.5:
S ABaC
A BC
B b |
C D |
D d
In step 2, variables B, C, and A (in that order) are added to VN
In step 3, -productions are eliminated
In step 4, productions are added by replacing nullable symbols with in all possible combinations, resulting in
S ABaC | BaC | AaC | Aba | aC | Aa | Ba | a
A B | C | BC
B b
C D
D d
Where did terminal a come from?
S -> ABaC -> BBaC -> a -> a
Unit-Productions
A production of the form A B (where A and B are variables) is called a unit-production
Unit-productions add unneeded complexity to a grammar and can usually be removed by simple substitution
Theorem 6.4 states that any context-free grammar without -productions has an equivalent grammar without unit-productions
The procedure for eliminating unit-productions assumes that all -productions have been previously removed
Removing Unit-Productions
Draw a dependency graph with an edge from A to B corresponding to every A B production in the grammar
Construct a new grammar that includes all the productions from the original grammar, except for the unit-productions
Whenever there is a path from A to B in the dependency graph, replace B using the substitution rule from Theorem 6.1, but using only the productions in the new grammar
Application of the Procedure for Removing Unit-Productions
Consider the grammar from example 6.6:
S Aa | B
A a | bc |B
B A | bb
The dependency graph contains paths from S to A, S to B, B to A, and A to B
After removing unit-productions and adding the new productions (in red), the resulting grammar is
S Aa | a | bc | bb
A a | bc | bb
B a | bc | bb
Simplification of Grammars
Theorem 6.5 states that, for any context-free language that does not include λ, there is a context-free grammar without useless, -, or unit-productions
Since the removal of one type of production may introduce productions of another type, undesirable productions should be removed in the following order:
Remove -productions
Remove unit-productions
Remove useless productions
Chomsky Normal Form
In Chomsky normal form, the number of symbols on the right side of a production is strictly limited.
A context-free grammar is in Chomsky normal form if all of its productions are in one of the forms below (A, B, C are variables; a is a terminal symbol)
A BC
A a
The grammar below is in Chomsky normal form
S AS | a
A SA| b
No mixing of variables and terminals! Much easier to read and interpret… but at a cost.
Transforming a Grammar into Chomsky Normal Form
For any context-free grammar that does not generate , it is possible to find an equivalent grammar in Chomsky normal form:
Copy any productions of the form A a
For other productions containing a terminal symbol x on the right side, replace x with a variable X and add the production X x
Introduce additional variables to reduce the lengths of the right sides of productions as necessary, replacing long productions with productions of the form W YZ (W, Y, Z are variables)
Application of the Procedure for Removing Unit-Productions
Consider the grammar from example 6.8, which is clearly not in Chomsky normal form
S ABa
A aab
B Ac
After replacing terminal symbols with new variables and adding new productions (in red), the resulting grammar is
S AC
C BX
A XD
D XY
B AZ
X a
Y b
Z c
The cost of ease of reading was 5 more productions!
Greibach Normal Form
In Greibach normal form, there are restrictions on the positions of terminal and variable symbols
A context-free grammar is in Greibach Normal Form if, in all of its productions, the right side consists of single terminal followed by any number of variables
.The grammar below is in Greibach normal form
S aAB | bBB | bB
A aA| bB | b
B b
Transforming a Grammar into Greibach Normal Form
For any context-free grammar that does not generate , it is possible to find an equivalent grammar in Greibach normal form
Consider the grammar from example 6.10, which is clearly not in Greibach normal form
S abSb | aa
After replacing terminal symbols with new variables and adding new productions (in red), the resulting grammar is
S aBSB | aA
A a
B b
Chapter 7
PUSHDOWN AUTOMATA
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Describe the components of a nondeterministic pushdown automaton
State whether an input string is accepted by a nondeterministic pushdown automaton
Construct a pushdown automaton to accept a specific language
Given a context-free grammar in Greibach normal form, construct the corresponding pushdown automaton
Describe the differences between deterministic and nondeterministic pushdown automata
Describe the differences between deterministic and general context-free languages
Classes of Automata
Increasing sophistication and capabilities
Nondeterministic Pushdown Automata
A pushdown automaton is a model of computation designed to process context-free languages
Pushdown automata use a stack as storage mechanism
Nondeterministic Pushdown Automata
A nondeterministic pushdown accepter (npda) is defined by:
A finite set of states Q
An input alphabet Σ
A stack alphabet Γ
A transition function δ
An initial state q0
A stack start symbol z
A set of final states F
Input to the transition function δ consists of a triple consisting of a state, input symbol (or ), and the symbol at the top of stack
Output of δ consists of a new state and new top of stack
Transitions can be used to model common stack operations
Sample npda Transitions
Example 7.1 presents the sample transition rule:
δ(q1, a, b) = {(q2, cd), (q3, )}
According to this rule, when the control unit is in state q1, the input symbol is a, and the top of the stack is b, two moves are possible:
New state is q2 and the symbols cd replace b on the stack
New state is q3 and b is simply removed from the stack
If a particular transition is not defined, the corresponding (state, symbol, stack top) configuration represents a dead state
Current state Input symbol Top of stack
New state New stack symbol
New state Clear stack symbol (e.g. pop function)
Set of transitions
A Sample Nondeterministic Pushdown Accepter
Example 7.2: Consider the npda
Q = { q0, q1, q2, q3 }, Σ = { a, b }, = { 0, 1 }, z = 0, F = {q3}
with initial state q0 and transition function given by:
δ(q0, a, 0) = { (q1, 10), (q3, ) }
δ(q0, , 0) = { (q3, ) }
δ(q1, a, 1) = { (q1, 11) }
δ(q1, b, 1) = { (q2, ) }
δ(q2, b, 1) = { (q2, ) }
δ(q2, , 0) = { (q3, ) }
As long as the control unit is in q1, a 1 is pushed onto the stack when an a is read
The first b causes control to shift to q2, which removes a symbol from the stack whenever a b is read
Transition Graphs
In the transition graph for a npda, each edge is labeled with the input symbol, the stack top, and the string that replaces the top of the stack
The graph below represents the npda in Example 7.2:
Transitions:
Current state Input symbol Stack top (current)
Input symbol stack top new stack top
Instantaneous Descriptions
To trace the operation of a npda, we must keep track of the current state of the control unit, the stack contents, and the unread part of the input string
An instantaneous description is a triplet (q, w, u) that describes state, unread input symbols, and stack contents (with the top as the leftmost symbol)
A move is denoted by the symbol ˫
A partial trace of the npda in Example 7.2 with input string ab is
(q0, ab, 0) ˫ (q1, b, 10) ˫ (q2, , 0) ˫ (q3, , )
Input symbol stack top (current)
new stack top
1 2 3
Current state Stack contents (left most is top)
Unread Input symbol
(left is beginning of tape)
1
2
3
Moves
The Language Accepted by a Pushdown Automaton
The language accepted by a npda is the set of all strings that cause the npda to halt in a final state, after starting in q0 with an empty stack.
The final contents of the stack are irrelevant
As was the case with nondeterministic automata, the string is accepted if any of the computations cause the npda to halt in a final state
The npda in example 7.2 accepts the language
{anbn: n ≥ 0} { a }
Pushdown Automata and Context-Free Languages
Theorem 7.1 states that, for any context-free language L, there is a npda to recognize L
Assuming that the language is generated by a context-free grammar in Greibach normal form, the constructive proof provides an algorithm that can be used to build the corresponding npda
The resulting npda simulates grammar derivations by keeping variables on the stack while making sure that the input symbol matches the terminal on the right side of the production
Construction of a Npda from a Grammar in Greibach Normal Form
The npda has Q = { q0, q1, qF }, input alphabet equal to the grammar terminal symbols, and stack alphabet equal to the grammar variables
The transition function contains the following:
A rule that pushes S on the stack and switches control to q1 without consuming input
For every production of the form A aX, a rule
δ (q1, a, A) = (q1, X)
A rule that switches the control unit to the final state when there is no more input and the stack is empty
Sample Construction of a NPDA from a Grammar
Example 7.6 presents the grammar below, in Greibach normal form
S aSA | a
A bB
B b
The corresponding npda has Q = { q0, q1, q2 } with initial state q0 and final state q2
The start symbol S is placed on the stack with the transition
δ(q0, , z) = { (q1, Sz) }
The grammar productions are simulated with the transitions
δ(q1, a, S) = { (q1, SA), (q1, ) }
δ(q1, b, A) = { (q1, B) }
δ(q1, b, B) = { (q1, ) }
A final transition places the control unit in its final state when the stack is empty
δ(q1, , z) = { (q2, ) }
Deterministic Pushdown Automata
A deterministic pushdown accepter (dpda) never has a choice in its move
Restrictions on dpda transitions:
Any (state, symbol, stack top) configuration may have at most one (state, stack top) transition definition
If the dpda defines a transition for a particular (state, λ, stack top) configuration, there can be no input-consuming transitions out of state s with a at the top of the stack
Unlike the case for finite automata, a -transition does not necessarily mean the automaton is nondeterministic
Example of a Deterministic Pushdown Automaton
Example 7.10 presents a dpda to accept the language
L = { anbn: n ≥ 0 }
The dpda has Q = { q0, q1, q2 }, input alphabet { a, b }, stack alphabet { 0, 1 }, z = 0, and q0 as its initial and final state
The transition rules are
δ(q0, a, 0) = { (q1, 10) }
δ(q1, a, 1) = { (q1, 11) }
δ(q1, b, 1) = { (q2, ) }
δ(q2, b, 1) = { (q2, ) }
δ(q2, , 0) = { (q0, ) }
Let’s create the transition graph for Example 7.10
Step 1
Add states with labels
Step 2
Add transitions between states, without labels.
Step 3
Add transition labels in the format:
Input, current stack top, new stack top
Deterministic Context-Free Languages
A context-free language L is deterministic if there is a dpda to accept L
Sample deterministic context-free languages:
{ anbn: n ≥ 0 }
{ wxwR: w {a, b}*}
Deterministic and nondeterministic pushdown automata are not equivalent: there are some context-free languages for which no dpda can be built
Chapter 9
TURING MACHINES
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Describe the components of a standard Turing machine
State whether an input string is accepted by a Turing machine
Construct a Turing machine to accept a specific language
Trace the operation of a Turing machine transducer given a sample input string
Construct a Turing machine to compute a simple function
State Turing’s thesis and discuss the circumstantial evidence supporting it
The Standard Turing Machine
A standard Turing machine has unlimited storage in the form of a tape consisting of an infinite number of cells, with each cell storing one symbol
The read-write head can travel in both directions, processing one symbol per move
A deterministic control function causes the machine to change states and possibly overwrite the tape contents
Input string is surrounded by blanks, so the input alphabet is considered a proper subset of the tape alphabet
Diagram of a Standard Turing Machine
In a standard Turing machine, the tape acts as the input, output, and storage medium.
Definition of a Turing Machine
A Turing Machine is defined by:
A finite set of internal states Q
An input alphabet Σ
A tape alphabet Γ
A transition function δ
A special symbol from Γ called the blank
An initial state q0
A set of final states F
Input to the transition function δ consists of the current state of the control unit and the current tape symbol
Output of δ consists of a new state, new tape symbol, and location of the next symbol to be read (L or R)
δ is a partial function, so that some (state, symbol) input combinations may be undefined
Sample Turing Machine Transition
Example 9.1 presents the sample transition rule:
δ(q0, a) = (q1, d, R)
According to this rule, when the control unit is in state q0 and the tape symbol is a, the new state is q1, the symbol d replaces a on the tape, and the read-write head moves one cell to the right
Sample Turing Machine Transition
Sample transition rule:
δ(q0, a) = (q1, d, R)
3
4
5
Order of: 1 2 3 4 5
Operations
0
1
A Sample Turing Machine
Example 9.2: Consider the Turing machine
Q = { q0, q1 }, Σ = { a, b }, = { a, b, }, F = { q1 }
with initial state q0 and transition function given by:
δ(q0, a) = (q0, b, R)
δ(q0, b) = (q0, b, R)
δ(q0, ) = (q1, , L)
The machine starts in q0 and, as long as it reads a’s, will replace them with b’s and continue moving to the right, but b’s will not be modified
When a blank is found, the control unit switches states to q1 and moves one cell to the left
The machine halts whenever it reaches a configuration for which δ is not defined (in this case, state q1)
Tracing the Operation of a Turing Machine
Figure 9.3 shows several stages of the operation of the Turing Machine in Example 9.2 as it processes a tape with initial contents aa
Transitions:
Transition Graphs for Turing Machines
In a Turing machine transition graph, each edge is labeled with three items:
current tape symbol
new tape symbol
direction of the head move
Figure 9.4 shows the transition graph for the Turing Machine in Example 9.2
Current symbol New symbol Direction
A Turing Machine that Never Halts
It is possible for a Turing machine to never halt on certain inputs, as is the case with Example 9.3 (below) and input string ab
The machine runs forever – in an infinite loop – with the read-write head moving alternately right and left, but making no modifications to the tape
Can we detect when this happens?
The Language Accepted by a Turing Machine
Turing machines can be viewed as language accepters
The language accepted by a Turing machine is the set of all strings which cause the machine to halt in a final state, when started in its standard initial configuration (q0, leftmost input symbol)
A string is rejected if
The machine halts in a nonfinal state, or
The machine never halts
Turing Machines as Transducers
Turing machines provide an abstract model for digital computers, acting as a transducer that transforms input into output
A Turing machine transducer implements a function that treats the original contents of the tape as its input and the final contents of the tape as its output
A function is Turing-computable if it can be carried out by a Turing machine capable of processing all values in the function domain
A Sample Turing Machine Transducer
Given two positive integers x and y in unary notation, separated by a single zero, the Turing machine below computes the function x + y
The transducer has Q = { q0, q1, q2, q3, q4 } with initial state q0 and final state q4
The defined values of the transition function are
δ(q0, 1) = (q0, 1, R) δ(q0, 0) = (q1, 1, R)
δ(q1, 1) = (q1, 1, R) δ(q1, ) = (q2, , L)
δ(q2, 1) = (q3, 0, L) δ(q3, 1) = (q3, 1, L)
δ(q3, ) = (q4, , R)
When the machine halts, the read-write head is positioned on the leftmost symbol of the unary representation of x + y
A Sample Turing Machine Transducer: Graph
δ(q0, 1) = (q0, 1, R)
δ(q0, 0) = (q1, 1, R)
δ(q1, 1) = (q1, 1, R)
δ(q1, ) = (q2, , L)
δ(q2, 1) = (q3, 0, L)
δ(q3, 1) = (q3, 1, L)
δ(q3, ) = (q4, , R)
Combining Turing Machines
By combining Turing Machines that perform simple tasks, complex algorithms can be implemented
For example, assume the existence of a machine to compare two numbers (comparer), one to add two numbers (adder), and one to erase the input (eraser)
Figure 9.8 shows the diagram of a Turing Machine that computes the function f(x, y) = x + y (if x ≥ y), 0 (if x < y)
Turing’s Thesis
How powerful are Turing machines?
Turing’s Thesis contends that any computation carried out by mechanical means can be performed by some Turing machine
An acceptance of Turing’s Thesis leads to a definition of an algorithm:
An algorithm for a function f : D R is a Turing machine M, which given any d D on its tape, eventually halts with the correct answer f(d) R on its tape
Evidence Supporting Turing’s Thesis
Anything that can be done on any existing digital computer can also be done by a Turing machine
No one has yet been able to suggest a problem, solvable by what we intuitively consider an algorithm, for which a Turing machine program cannot be written
Alternative models have been proposed for mechanical computation, but none of them is more powerful than the Turing machine model
Chapter 12
LIMITS OF ALGORITHMIC COMPUTATION
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Explain and differentiate the concepts of computability and decidability
Define the Turing machine halting problem
Discuss the relationship between the halting problem and recursively enumerable languages
Give examples of undecidable problems regarding Turing machines to which the halting problem can be reduced
Give examples of undecidable problems regarding recursively enumerable languages
Determine if there is a solution to an instance of the Post correspondence problem
Give examples of undecidable problems regarding context-free languages
Computability and Decidability
Are there questions which are clearly and precisely stated, yet have no algorithmic solution?
As stated in chapter 9, a function f is computable if there exists a Turing machine that computes the value of f for all arguments in its domain
Since there may be a Turing machine that can compute f for part of the domain, it is crucial to define the domain of f precisely
The concept of decidability applies to computations that result in a “yes” or “no” answer: a problem is decidable if there exists a Turing machine that gives the correct answer for every instance in the domain
The Turing Machine Halting Problem
The Turing machine halting problem can be stated as: Given the description of a Turing machine M and an input string w, does M perform a computation that eventually halts?
The domain of the problem is the set of all Turing machines and all input strings w
Any attempts to simulate the computation on a universal Turing machine face the problem of not knowing if/when M has entered an infinite loop
By Theorem 12.1, there does not exist any Turing machine that finds the correct answer in all instances; the halting problem is therefore undecidable
The Halting Problem and Recursively Enumerable Languages
Theorem 12.2 states that, if the halting problem were decidable, then every recursively enumerable language would be recursive
Assume that L is a recursively enumerable language and M is a Turing machine that accepts L
If H is a Turing machine that solves the halting problem, then we can apply H to the accepting machine M
If H concludes that M does not halt, then by definition the input string is not in L
If H concludes that M halts, then M will determine if the input string is in L
Consequently, we would have a membership algorithm for L, but we know that one does not exist for some recursively enumerable languages, therefore contradicting our assumption that H exists
Reducing One Undecidable Problem to Another
A problem A is reduced to a problem B if the decidability of A follows from the decidability of B
An example is the state-entry problem: given any Turing machine M and string w, decide whether or not the state q is ever entered when M is applied to w
If we had an algorithm that solves the state-entry problem, it could be used to solve the halting problem
However, because the halting problem is undecidable, the state-entry problem must also be undecidable
The Blank-Tape Halting Problem
Given a Turing machine M, determine whether or not M halts if started with a blank tape
To show that the problem is undecidable,
Given a machine M and input string w, construct from M a new machine Mw that starts with a blank tape, writes w on it, and acts like M
Clearly, Mw will halt on a blank tape if and only if M halts on w
If we start with Mw and apply the blank-tape halting problem algorithm to it, we would have an algorithm for the halting problem
Since the halting problem is known to be undecidable, the same must be true for the blank-tape version
The Undecidability of the Blank-Tape Halting Problem
Figure 12.3 illustrates the process used to establish the result that the blank-tape halting problem is undecidable
After Mw is built, the presumed blank-tape halting problem algorithm would be applied to Mw, yielding an algorithm for the halting problem, which leads to a contradiction
Is the Language Accepted by a Turing Machine finite?
Given a Turing machine M, determine whether or not L(M) is finite
To show that the problem is undecidable,
Given a Turing machine M and string w, modify M to create a new machine M^, so that if any halting state of M is reached, M^ accepts all input
Have M^ generate w on an unused portion of its tape and perform the same computations as M, so that
if M halts in any configuration, then M^ halts in a final state, and
If M does not halt, then M^ will not halt either
As a result, M^ either accepts or the infinite language +
Assuming there is an algorithm A for deciding whether or not L(M) is finite, we could apply it to M^, which would give us a solution to the halting problem
But this contradicts previous results that have established that the halting problem is undecidable
The Undecidability of the “L(M) is Finite” Problem
Figure 12.6 illustrates the process used to establish the result that the “L(M) is finite” question is undecidable
After an algorithm generates M^, the presumed finiteness algorithm A would be applied to M^, resulting in a solution to the halting problem, which is impossible
The Post Correspondence Problem
Given two sequences of n strings on some alphabet , for instance
A = w1, w2, …, wn and B = v1, v2, …, vn
there is a Post correspondence solution (PC solution) for the pair (A, B) if there is a nonempty sequence of integers i, j, …, k, such that wiwj…wk = vivj…vk
As shown in Example 12.5, assume A and B consist of
w1 = 11, w2, = 100, w3 = 111 and v1 = 111, v2, = 001, v3 = 11
A PC solution for this instance of (A, B) exists, as shown below
The Undecidability of the Post Correspondence Problem
The Post correspondence problem is to devise an algorithm that determines, for any (A, B) pair, whether or not there exists a PC solution
For example, there is no PC solution if A and B consist of
w1 = 00, w2, = 001, w3 = 1000 and v1 = 0, v2, = 11, v3 = 011
Theorem 12.7 states that there is no algorithm to decide if a solution sequence exists under all circumstances, so the Post correspondence problem is undecidable
Although a proof of theorem 12.7 is quite lengthy, this very important result is crucial for showing the undecidability of various problems involving context-free languages
Undecidable Problems for Context-Free Languages
The Post correspondence problem is a convenient tool to study some questions involving context-free languages
The following questions, among others, can be shown to be undecidable
Given an arbitrary context-free grammar G, is G ambiguous?
Given arbitrary context-free grammars G1 and G2,
is L(G1) L(G2) = ?
Given arbitrary context-free grammars G1 and G2,
is L(G1) = L(G2)?
Given arbitrary context-free grammars G1 and G2,
is L(G1) L(G2)?
Other Undeciable Problems
Determining whether a Turing machine is a busy beaver champion
i.e., is the longest-running among halting Turing machines with the same number of states.
Rice's theorem states that for all nontrivial properties of partial functions, it is undecidable whether a given machine computes a partial function with that property.
The halting problem for a Minsky machine: a finite-state automaton with no inputs and two counters that can be incremented, decremented, and tested for zero.
Universality of a Nondeterministic Pushdown automaton: determining whether all words are accepted.
So why is the Halting Problem so Important?
A lot of really practical problems are the halting problem in disguise. A solution to them solves the halting problem.
You want a compiler that finds the fastest possible machine code for a given program? Actually the halting problem.
You have JavaScript, with some variables at a high security levels, and some at a low security level. You want to make sure that an attacker can't get at the high security information. This is also just the halting problem.
You have a parser for your programming language. You change it, but you want to make sure it still parses all the programs it used to. Actually the halting problem.
You have an anti-virus program, and you want to see if it ever executes a malicious instruction. Actually just the halting problem.
So why is the Halting Problem so Important?
The Halting problem lets us reason about the relative difficulty of algorithms. It lets us know that, there are some algorithms that don't exist, that sometimes, all we can do is guess at a problem, and never know if we've solved it.
What's at the core of undecidability is really having an infinite search space. You're searching for an object with a given property, and if one doesn't exist, there's no way to know when you're done.
Joey Eremondi, PhD Student @ University of British Columbia, 2014
Chapter 14
AN OVERVIEW OF COMPUTATIONAL COMPLEXITY
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Explain the concept of computational complexity as it relates to Turing machines
Describe deterministic and nondeterministic solutions to the SAT problem
Determine if a Boolean expression in CNF is satisfiable
Describe the efficiency of standard Turing machines that simulate two-tape machines and of those that simulate nondeterministic machines
Define the complexity classes P and NP, as well as the relationship between P and NP
Explain the concepts of intractability and NP-completeness
List some well-known NP-complete problems
Discuss the significance and status of the P = NP? question
Efficiency of Computation
Computational complexity is the study of the efficiency of algorithms
When studying the time requirements of an algorithm, the following assumptions are made:
The algorithm will be modeled by a Turing machine
The size of the problem will be denoted by n
When analyzing an algorithm, the focus is on its general behavior, particularly as the size of the problem increases
A computation has time-complexity T(n) if it can be completed in no more than T(n) moves on some Turing machine
Turing Machine Models and Complexity
Although different models of Turing machines are equivalent, the efficiency of a computation can be affected by the number of tapes available and by whether it is deterministic or nondeterministic
Consider the Satisfiability Problem (SAT): given a Boolean expression e in conjunctive normal form, find an assignment of values to the variables so that e is true
For example, the expression e1 = (x1’ x2) (x1 x3) is true when x1 = 0, x2 = 1, and x3 = 1
However, the expression e2 = (x1 x2) x1’ x2’ is not satisfiable
Solving the Satisfiability Problem
A deterministic algorithm would take all possible values for the n variables and evaluate the expression for each combination
Since there are 2n possibilities, the deterministic solution has exponential time complexity
A nondeterministic algorithm would guess the value of each of the n variables at each step and evaluate each of the 2n possibilities simultaneously, thus resulting in an O(n) algorithm
There is no known nonexponential deterministic algorithm for solving the SAT problem
Simulation of a Two-Tape Machine
Theorem 14.1 states that, if a two-tape machine can carry out a computation in n steps, the computation can be simulated by a standard Turing machine in O(n2) moves
To simulate the two-tape computation, the standard machine would
Keep a description of the two-tape machine on its tape
For each two-tape move, search the entire active area of its tape
After n moves, the active area has a length of at most O(n), so the entire simulation takes O(n2) moves
Simulation of a Nondeterministic Machine
Theorem 14.2 states that, if a nondeterministic machine can carry out a computation in n steps, the computation can be carried out by a standard Turing machine in O(kan) moves, where k and a are independent of n
To simulate the nondeterministic computation, the standard machine would keep track of all possible configurations, searching and updating the entire active area of its tape
If k is the maximum branching factor for the nondeterministic machine, after n steps there are at most kn possible configurations, and the length of each configuration is O(n)
Therefore, to simulate one move, the standard machine must search an active area of length O(nkn)
Considerations Affecting Complexity Classes and Languages
It is difficult to classify languages by the complexity classes associated with the corresponding Turing machine acceptors
Since the particular model of Turing machine used affects the complexity of the associated algorithms, it is difficult to determine which variation to use as the best model of an actual computer
The efficiency differences between deterministic and nondeterministic algorithms can be much more significant than differences between alternative deterministic algorithms involving different numbers of available tapes
The Complexity Classes P and NP
There are two famous complexity classes associated with languages: P and NP
P is the set of all languages that are accepted by some deterministic Turing machine in polynomial time, without any regard to the degree of the polynomial
NP is the set of all languages that are accepted by some nondeterministic Turing machine in polynomial time
The Relationship Between P and NP
Obviously, P NP (P is a subset of NP)
What is not known is whether P is a proper subset of NP, in other words,
is P NP or P = NP?
While it is generally believed that there are languages in NP which are not in P, no one has yet found a conclusive example
Because of its significance on the feasibility of certain computations, this question remains the most fundamental unresolved problem in theoretical computer science
Intractability
A problem is intractable if it has such high resource requirements that practical solutions are unrealistic, although the problem may be computable in principle
Algorithms for solving intractable problems consume an extraordinary amount of time for nontrivial values of n on any computer available now or in the foreseeable future
According to the Cook-Karp thesis, a problem in P is tractable, and one not in P is intractable
Some NP Problems
The following problems, among others, can be solved nondeterministically in polynomial time:
The Satisfiability problem
The Hamiltonian path problem: given an undirected graph with n vertices, find a simple path that passes through all the vertices
The Clique problem: given an undirected graph with n vertices, find a subset of k vertices such that there is an edge between every pair of vertices in the subset
These problems have deterministic solutions with exponential time complexity, but no deterministic polynomial solution has been found
Polynomial-Time Reduction
Since NP problems have similar characteristics, it is convenient to determine if they can be reduced to each other
A language L1 is polynomial-time reducible to another language L2 if there exists a deterministic Turing machine that can transform any string w1 in L1 to a string w2 in L2 so that
The transformation can be completed in polynomial time, and
w1 is in L1 if and only if w2 is in L2
Consider 3SAT, a modified version of the SAT problem in which each clause can have at most three literals; as shown in Examples 14.9 and 14.10,
The SAT problem is polynomial-time reducible to 3SAT
The 3SAT problem is polynomial-time reducible to CLIQUE
NP-Completeness
Some problems have been identified as being as complex as any other problem in NP
A language (or problem) L is NP-complete if
L is in NP, and
Every problem in NP is polynomial-time reducible to L
As stated in Theorem 14.5, the Satisfiability Problem is NP-complete
This definition is very significant because, if a deterministic polynomial-time algorithm is found for any NP-complete problem, then every language in NP is also in P
“Every Day” NP-Hard Problems
Assigning university classes to timeslots to minimize scheduling conflicts.
Assigning wedding guests to seats so that friends sit at the same table, but enemies do not.
Planning a road trip to visit all of the tourist spots on a list, so as to minimize driving.
Many problems that are related to optimization, scheduling, or have a high degree of dynamism between steps are NP-Hard. We can only find approximate, or “good enough”, solutions to these problems.
An Open Question: P = NP?
Computer scientists continue to look for an efficient (deterministic, polynomial-time) algorithm that can be applied to all NP problems, therefore concluding that P = NP
On the other hand, if a proof is found that any of the NP-complete problems is intractable, then we can conclude that P NP and that many interesting problems are not practically solvable
In spite of our best efforts, no efficient algorithm has been found for any NP-complete problem, so our conjecture is that P NP
However, until a proof is found, P = NP? remains the fundamental open question in complexity theory
?
/docProps/thumbnail.jpeg