MRECW Students E- Learning Point Computer Security Student (CSS)

Theroy of Computation

TURING MACHINE

1. A Universal Turing Machine can compute anything that any other Turing Machine could possibly compute.
True

2.The Turing Test is a test of whether a problem can be solved by a Turing Machine.
True

3. Every acceptable language is also decidable.
False

4. Decidability is a special case of decidability
True

5. Regular languages are decidable
True

6. Context free languages are not decidable
False

DFA MINIMIZATION

DFA MINIMIZATION EXAMPLES

1. Example 1
2. Example2

 

Chomsky Hierarchy

The diagram shows how different classes of languages such as regular, context free, context sensitive, P, NP, PSAPACE, NPSPACE, EXPTIME, NEXPTIME, EXPSPACE, ACCEPTABLE, DECIDABLE, CO-ACCEPTABLE etc are related to each other.

PUMPPING LEMMA

Steps to solve Pumping Lemma problems:
1. If the language is finite, it is regular , otherwise it might be non-regular.
2. Consider the given language to be regular
3. State pumping lemma
4. Choose a string w from language, choose smartly .
5. Partition it according to constraints of pumping lemma in a generic way
6. Choose a pumping factor k such that the new ‘pumped’ string is not part of the language
given.
7. State the contradiction and end the proof.

How to remember what pumping Lemma says:

Pumping Lemma alternates between “for all” and “there is at least one” or “for every” or
“there exists”. Notice:
For every regular language L
There exists a constant n
For every string w in L such that |w| >= n,
There exists a way to break up w into three strings w = xyz such that |y| > 0 , |xy| <= n and For every k>=0 , the string xykz is also in L.

courtesey: http://suraj.lums.edu.pk/~cs311w05/pumping_lemma_writeup.pdf
1. Show that L2 = {0^m1^m | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L1. Consider any pumping number p; p≥ 1. Choose w = 0^p1^p.
Consider any pumping decomposition w = xyz;
|y| > 0 and |xy| ≤ p. It follows that x = 0^a and y = 0^b and z = 0^p-a-b1^p, for b ≥ 1. Choose i = 2. We need to show that xy²z = 0^p+b1^p is not in L1.

b ≥ 1.
So p+b > p
Hence 0^p+b1^p is not in L.

2. L2 = {xx | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L2. Consider any pumping number
p ≥ 1. Choose w = 10^p10^p. Consider any pumping decomposition w = xyz; all we know about xyz is that
|y| > 0 and |xy| ≤ p. There are two possibilities:

(a) x = 10^aand y = 0^b and z = 0^p-a-b10^p, for b ≥ 1.
(a) x = " and y = 10b and z = 0^p-b10^p1.
Choose i = 2. We need to show that xy²z is not in L2.
In case (a), xy2z = 10^p+b10^p, which is not in L2 because b ≥ 1.
In case (b), xy2z = 10^b10^p10^p, which is not in L2 because it contains three 1’s.

3. We prove that L3 = {1ⁿ² | n ≥ 0} is not regular.

We show that the pumping lemma does not hold for L3. Consider any pumping number p ≥ 1.
Choose w = 1^p2.
Consider any pumping decomposition w = xyz such that |y| > 0 and |xy| ≤ p. It follows
that x = 1^a and y = 1^b and z = 1^p2
−a−b, for b ≥ 1 and a + b ≤ p. Choose i = 2. We need to show that
xy²z = 1^n2+b is not in L3; that is, we need to show that p2 + b is not a square. Since b ≥ 1, we have
p2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 4.Prove that Language L = {0n: n is a perfect square} is irregular.

Solution: L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such that:
|y| > 0 , |xy| <= n and for all k>=0 , the string xy^kz is also in L.
Choose w to be w = 0s where s = n² that is it is a perfect square.
Let w= 00000000000000000………00000 = xyz . (The length of w = s = n² in this case.)
Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n²- k ) + (k) From pumping lemma, I can pump y any number of times and the new string should also belong to the language. Suppose I pump y twice then, the new string should belong to the language that is it should have length that is a perfect square but, |xy2z| = |xz| + 2|y| = (n²- k ) + 2k = n² + k where n² + k < 1 =" (n+1)(n+1)"> n² (As k > 0)
=> n² <>2 + k < (n+1)2 => n² + k is not a perfect square
=> xy²z is not in L
=> This is a contradiction to the pumping lemma
So, our initial assumption must have been wrong that is L is not regular.