This document discusses decidability and undecidability of formal languages. It defines recursive, recursively enumerable, decidable, and undecidable languages. A language is decidable if there exists an algorithm that accepts all strings in the language and rejects all strings not in it. The halting problem is provided as an example of an undecidable problem. The document also proves several properties of recursive and recursively enumerable languages, including that the union of two recursive (recursively enumerable) languages is recursive (recursively enumerable) and that a language is recursive if both it and its complement are recursively enumerable.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PPT, PDF, TXT or read online from Scribd
This document discusses decidability and undecidability of formal languages. It defines recursive, recursively enumerable, decidable, and undecidable languages. A language is decidable if there exists an algorithm that accepts all strings in the language and rejects all strings not in it. The halting problem is provided as an example of an undecidable problem. The document also proves several properties of recursive and recursively enumerable languages, including that the union of two recursive (recursively enumerable) languages is recursive (recursively enumerable) and that a language is recursive if both it and its complement are recursively enumerable.
This document discusses decidability and undecidability of formal languages. It defines recursive, recursively enumerable, decidable, and undecidable languages. A language is decidable if there exists an algorithm that accepts all strings in the language and rejects all strings not in it. The halting problem is provided as an example of an undecidable problem. The document also proves several properties of recursive and recursively enumerable languages, including that the union of two recursive (recursively enumerable) languages is recursive (recursively enumerable) and that a language is recursive if both it and its complement are recursively enumerable.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PPT, PDF, TXT or read online from Scribd
This document discusses decidability and undecidability of formal languages. It defines recursive, recursively enumerable, decidable, and undecidable languages. A language is decidable if there exists an algorithm that accepts all strings in the language and rejects all strings not in it. The halting problem is provided as an example of an undecidable problem. The document also proves several properties of recursive and recursively enumerable languages, including that the union of two recursive (recursively enumerable) languages is recursive (recursively enumerable) and that a language is recursive if both it and its complement are recursively enumerable.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
You are on page 1/ 10
Unit V
D. Jagadeesan
Undecidability
Basic Definition
Phrase Structure Grammar
It consists of four components G = ( V, T, P, S )
Recursive Language
A language is recursive if there exists a Turing Machine that accepts every string of the language and reject every string that is not in the language. w
Yes No
Recursively Enumerable Language
A language is recursive enumerable if there exists a Turing Machine that accepts every string of the language and does not accept strings that are not in the language. The strings that are not in the language may be rejected and it may cause the TM to go to an infinite loop. w
Yes Infinite loop
Basic Definition
Decidability
A language is decidable (recursive) if and only if there is a TM M such that M accepts every string in L and rejects every string not in L or A problem whose language is recursive is said to be a decidable.
Example :
The strings over {a,b} that consists of alternating as and bs.
The strings over {a,b} that contains an equal number of as and bs
Basic Definition
Undecidability A
problem is undecidable, if there is no algorithm, that can take as input an instance of the problem and determines whether the answer to that instance is Yes or No. Given a TM M and an input string w, does M halt on input w? (Halting Problem) For a fixed machine M, given an input string w, does M halt on input w?
Example :
Membership problem is undecidable.
State entry problem is undecidable.
Properties of Recursive and Recursively Enumerable Languages
Union of two recursive languages is recursive. Union of two recursive enumerable languages is also recursively enumerable. Complement of a recursive language is recursive. L if L and complement of L (L) are recursively enumerable is recursive.
Union of two recursive languages is recursive.
Theorem : The Complement of recursive language is recursive.
Proof : Let L be a recursive language. Then there exists a TM M that halts on every string on L. L = * - L
Since L is recursive there is an algorithm (TM M) to accept L. Now construct an algorithm (TM M) for L is as follows.
Yes No
Yes
No
If M halts without accepting the string, then M halts accepting that string and if M halts on accepting it, M enters into the final state without accepting it. Clearly L(M) is the complement of L and thus L is a recursive language.
Union of two recursive languages is recursive.
Theorem : If L1 and L2 are two recursive languages then L1 U L2 is also a recursive language.
Proof : Let L1 and L2 be recursive languages accepted by the TMs M1 and M2 respectively. Construct a new TM M which first simulates M1. If M1 accepts, then M accepts. If M1 reject, the simulates M2 and accepts if and only if M2 accepts. Thus M has both accepting and rejecting criterion. So, M accepts L1 U L2. recursive w Yes No
M1w
M2 recursive
Yes
Yes recursive No
Union of two recursively enumerable languages is recursive.
Theorem : If L1 and L2 are two recursively enumerable languages then L1 U L2 is also a recursively enumerable language.
Proof : Let L1 and L2 be recursively enumerable languages accepted by the TMs M1 and M2 respectively. Construct a new TM M which simultaneously simulates M1 and M2 on different tapes. If M1 or M2 accepts, the M accepts. recursively enumerable w
M1 M2
M Yes
Yes
Yes
Recursive enumerable
recursively enumerable
L if L and complement of L (L) are recursively enumerable is recursive.
Theorem : L if L and complement of L (L) are recursively enumerable is recursive.
Proof : Let M1 and M2 be the TMs designed for the languages L and L respectively. Construct a new TM M which simulates M1 and M2 simultaneously. If M accepts w if M1 accepts w, M rejects w if M2 accepts w.
M1 M2
M Yes Yes
Recursive Yes No
L if L and complement of L (L) are recursively enumerable is recursive.
Theorem : L if L and complement of L (L) are recursively enumerable is recursive.
Proof : Let M1 and M2 be the TMs designed for the languages L and L respectively. Construct a new TM M which simulates M1 and M2 simultaneously. If M accepts w if M1 accepts w, M rejects w if M2 accepts w.
(Logic, Epistemology, and The Unity of Science 28) Fabrice Pataut (Eds.) - Truth, Objects, Infinity - New Perspectives On The Philosophy of Paul Benacerraf (2016, Springer International Publishing)
(Logic, Epistemology, and The Unity of Science 28) Fabrice Pataut (Eds.) - Truth, Objects, Infinity - New Perspectives On The Philosophy of Paul Benacerraf (2016, Springer International Publishing)
