FIT2014 Theory of Computation Lecture 20 University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 20
Decidability
slides by
based in part on previous slides by
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 18
Overview
I Decision problems
I Decidable problems and languages
I Deciders
I Closure
2 / 18
Deciders
Reminder:
A decider is a Turing Machine that halts for every input.
A language is decidable if it is Accept(L) for some decider.
. . . in which case, its complement is Reject(L) for the same decider.
Examples:
I Regular Languages
I Context Free Languages
I {anbnan : n ≥ 0}
3 / 18
Decidable: synonyms
decidable
= recursive
= solvable
= computable
. . . sometimes, though “computable” has
been used with other meanings too.
4 / 18
Decision Problems
Input: an integer
Question: Is it even?
Input: a string.
Question: Is it a palindrome?
Input: an expression in propositional logic
Question: Is it ever True?
Input: a graph G , and two vertices s and t
Question: is there a path from s to t in G ?
Input: a Python program
Question: is it syntactically correct?
5 / 18
Input: a Finite Automaton
Question: Does it define the empty language?
Input: two Regular Expressions
Question: Do they define the same language?
Input: a Finite Automaton
Question: Does it define an infinite language?
Input: a Context Free Grammar
Question: Does it define the empty language?
Input: a Context Free Grammar
Question: Does it generate an infinite language?
Input: a Context Free Grammar and a string w
Question: Can w be generated by the grammar?
6 / 18
Decision Problems
A decision problem is a problem where, for each input, the answer is Yes or No.
A decider solves a decision problem if it
I Accepts an input for which the answer is Yes, and
I Rejects any input for which the answer is No.
Decision problem −→ language
I { YES-inputs }
Language −→ decision problem
I Input: a string
(over some alphabet, usually representing some object)
Question: Is the string in the Language?
Thus, a decider solves a decision problem if and only if it is a decider for its
corresponding language.
7 / 18
Encoding of Input
The input and output for a Turing Machine is always a string.
For any object, O, 〈O〉 will denote encoding of the object as a string.
If we have several objects, O1, . . . ,On, we denote their encoding into a single string by
〈O1, . . . ,On〉 .
8 / 18
Testing Emptiness of Regular Languages
Decision Problem:
Input: a Finite Automaton
Question: Does it define the empty language?
Language:
FA-Empty := {〈A〉 : A is a FA and L(A) = ∅}
Theorem.
FA-Empty is decidable.
9 / 18
Testing Emptiness of Regular Languages
Theorem.
FA-Empty is decidable.
Proof. (outline)
Algorithm:
Input: 〈A〉 where A is a Finite Automaton.
1. Mark the Start State of A.
2. Repeat until no new states get marked:
I Mark any state that has a transition coming into it from any state that is already
marked.
I If no final state is marked, Accept; otherwise Reject.
10 / 18
Testing Equivalence of Regular Expressions
Decision Problem:
REGULAR EXPRESSION EQUIVALENCE
Input: two Regular Expressions
Question: Do they define the same language?
For a Regular expression R, let L(R) be the language defined by R.
Language:
RegExpEquiv := {〈A,B〉 : A,B are regular expressions and L(A) = L(B)}
Theorem.
RegExpEquiv is decidable.
11 / 18
Testing Equivalence of Regular Expressions
Proof.
Algorithm:
Input: 〈A,B〉 where A and B are regular expressions
1. Construct a FA, C , that defines the language
(L(A) ∩ L(B)) ∪ (L(A) ∩ L(B)).
2. Run the previous Turing Machine, T , on C .
3. If T accepts C , then Accept, else Reject.
12 / 18
Testing Emptiness of Context Free Language
Decision Problem:
Input: a Context Free Grammar
Question: Does it define the empty language?
Language:
CFG-Empty := {G : G is a CFG and G defines the empty language}
Theorem.
CFG-Empty is decidable.
13 / 18
Testing Emptiness of Context Free Language
Algorithm:
Input: 〈A〉 where A is a Context Free Grammar.
1. Mark all the terminal symbols in A.
2. Repeat until no new symbols get marked:
I Mark any non-terminal X that has a production which has all the right-hand
symbols marked.
I If Start Symbol is not marked, Accept, else Reject.
14 / 18
Some Decidable Problems
Input: a Finite Automaton
Question: Does it define the empty language?
Input: two Regular Expressions
Question: Do they define the same language?
Input: a Finite Automaton
Question: Does it define an infinite language?
Input: a Context Free Grammar
Question: Does it define the empty language?
Input: a Context Free Grammar
Question: Does it generate an infinite language?
Input: a Context Free Grammar and a string w
Question: Can w be generated by the grammar? 15 / 18
Language classes
Decidable
CFLs
regular
languages
?
16 / 18
Closure properties
If L is decidable, then L is decidable.
If L1 and L2 are decidable, then so are
I L1 ∪ L2
I L1 ∩ L2
I L1L2
I . . .
Exercise:
Formulate and prove more closure results.
17 / 18
Revision
I Decidable Problems, decidable languages, and the link between them.
I Decision problems, relationship with languages
I Examples of Decidable Problems.
I Closure properties
Reading: Sipser, Section 4.1, pp. 190–201.
Preparation: Sipser, Section 4.2, pp. 201–213, especially pp. 207–209.
18 / 18