FIT2014 Lecture Notes - Lecture 16: Terminal And Nonterminal Symbols, Natural Number, L(R)
29 Jun 2018
School
Department
Course
Professor
Lecture 16
Decidability
Decision Problem:
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
uestion: is there a path from s to t in G ?
Input: a Java program
Question: is it syntactically correct?
Decision Problems
A decision problem is a problem where, for each input, the answer is yes or no.
Decision problem language { YES-inputs}
Language decision problem
Input: a string (over some alphabet, usually representing some object) Question: Is the string in the Language?
A decision problem is decidable if there is an algorithm that solves it i.e. correctly provides a yes or no answer
in a finite number of steps.
A language is decidable if there is an algorithm that solves i.e. correctly tells whether or not something is in
the language, in a finite number of steps
Encoding of Input
The input and output for a Turing Machine is always a string
For any objext O, <O> will denote encoding of the object as a string. If we have several objects, O1, ..On, will
denote their encoding into a single string.
Deciders
A decider is a Turing Machine that halts for any input over a given alphabet, and has two possible outputs -
either a <yes> or <no>
Decidable Languages
A decidable language consists of all those inputs for a decider that halt with a <yes>
- Regular language
o A finite automaton form a regular language.
o Finite automaton with a Turing machine
- Context free language
o Pushdown automaton can always recognise some string
- Anbnan: using pumping lemma for regular and context free and see that it is not both. However it is
decidable
Document Summary
A decision problem is a problem where, for each input, the answer is yes or no. A decision problem is decidable if there is an algorithm that solves it i. e. correctly provides a yes or no answer in a finite number of steps. A language is decidable if there is an algorithm that solves i. e. correctly tells whether or not something is in the language, in a finite number of steps. The input and output for a turing machine is always a string. For any objext o, will denote encoding of the object as a string. If we have several objects, o1, on, will denote their encoding into a single string. A decider is a turing machine that halts for any input over a given alphabet, and has two possible outputs - either a or A decidable language consists of all those inputs for a decider that halt with a
