Scribd
Upload
15 views1 page

Toc Assignment 3

Uploaded by

Ronit Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views1 page

Toc Assignment 3

Uploaded by

Ronit Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment: -04

Que1) Explain Pumping Lemma theorem for Context


Free Language with example.
Que2) Define the following: -
• Universal Turing Machine (UTM)
• Church Turing Thesis
• Halting /Halt Problem
• Solvability
• Decidability/Undecidability
Que3) What do you understand by post correspondence
problem (PCP)?

You might also like