Scribd
Upload
211 views

Toc Unit Iv

The document discusses the pumping lemma for context-free languages. It explains that for any context-free language L, there exists an integer n such that any string z in L of length greater than or equal to n can be divided into uvwxy where |vwx| ≤ n, |vx| > 0, and uviwxi y is in L for all i ≥ 0. It then provides an example of using the pumping lemma to show that the language L={xnynzn|n≥1} is not context-free by considering different cases of dividing the string that lead to a contradiction.

Uploaded by

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

Toc Unit Iv

The document discusses the pumping lemma for context-free languages. It explains that for any context-free language L, there exists an integer n such that any string z in L of length greater than or equal to n can be divided into uvwxy where |vwx| ≤ n, |vx| > 0, and uviwxi y is in L for all i ≥ 0. It then provides an example of using the pumping lemma to show that the language L={xnynzn|n≥1} is not context-free by considering different cases of dividing the string that lead to a contradiction.

Uploaded by

Deva Raj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

Pumping lemma for context free languages.

For every CFL L there is an integer n, such that for every string z in L of length ≥ n, there exists z = uvwxy
such that:
• |vwx| ≤ n.
• |vx| > 0.
• For all i ≥ 0, uviwxi y ∈ L

The steps to prove that the language is not a context free by using pumping lemma are explained below −

 Assume that L is context free.


 The pumping length is n.
 All strings longer than n can be pumped |w|>=n.
 Now find a string 'w' in L such that |w|>=n.
 Divide w into uvxyz
 Show that uvkxykz ∉L for some k
 Then, consider the ways that w can be divided into uvxyz.
 Show that none of these can satisfy all the 3 pumping conditions at same time.
 w cannot be pumped (contradiction).

Example
Find out whether L={xnynzn|n>=1} is context free or not

Solution

 Let L be context free.


 L must satisfy pumping length, say n.
 Now we can take a string such that s=xnynzn
 We divide s into 5 strings uvxyz.

Let n=4 so, s=x4y4z4

Case 1:
v and y each contain only one type of symbol.
{we are considering only v and y because v and y has power uv2xy2z}
X xx x yyyyz z zz
=uvkxykz when k=2
=xxxxxxyyyyzzzzz
=x6y4z5
(Number of x # number of y #number of z)
Therefore,The resultant string is not satisfying the condition
x6y4z5 ∉ L
If one case fails then no need to check another condition.

Case 2:
Either v or y has more than one kind of symbols
Xx xx yy y y zzzz
=uvkxykz (k=2)
=uv2xy2z
=xxxxyyxxyyyyyzzzz
=x4y2x2y5z2
This string is not following the pattern of our string x nynzn

Closure Properties of CFLs


A closure property of a language class says that given languages in the class, an operator (e.g., union)
produces another language in the same class.

Union : If L1 and L2 are two context free languages, their union L1 ∪ L2 will also be context free. For example, 
L1 = { anbncm | m >= 0 and n >= 0 } and L2 = { a nbmcm | n >= 0 and m >= 0 } 
L3 = L1 ∪ L2 = { anbncm ∪ anbmcm | n >= 0, m >= 0 } is also context free. 
L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of
c’s. Their union says either of two conditions to be true. So it is also context free language. 
Note: So CFL are closed under Union. 
  
Concatenation : If L1 and If L2 are two context free languages, their concatenation L1.L2 will also be context free.
For example, 
L1 = { anbn | n >= 0 } and L2 = { c mdm | m >= 0 } 
L3 = L1.L2 = { anbncmdm | m >= 0 and n >= 0} is also context free. 
L1 says number of a’s should be equal to number of b’s and L2 says number of c’s

should be equal to number of d’s. Their concatenation says first number of a’s should be equal to number of b’s,

then number of c’s should be equal to number of d’s. So, we can create a PDA which will first push for a’s, pop for

b’s, push for c’s then pop for d’s. So it can be accepted by pushdown automata, hence context free.
Note: So CFL are closed under Concatenation. 
  
Kleene Closure : If L1 is context free, its Kleene closure L1* will also be context free. For example, 
L1 = { anbn | n >= 0 } 
L1* = { anbn | n >= 0 }* is also context free. 
Note :So CFL are closed under Kleen Closure. 

Intersection and complementation : If L1 and If L2 are two context free languages, their intersection L1 ∩ L2
need not be context free. For example, 
L1 = { anbncm | n >= 0 and m >= 0 } and L2 = (a mbncn | n >= 0 and m >= 0 } 
L3 = L1 ∩ L2 = { anbncn | n >= 0 } need not be context free. 
L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of
c’s. Their intersection says both conditions need to be true, but push down automata can compare only two. So it
cannot be accepted by pushdown automata, hence not context free. 
Similarly, complementation of context free language L1 which is ∑* – L1, need not be context free. 
Note : So CFL are not closed under Intersection and Complementation. 

Decision Properties of CFLs:


A decision property for a class of languages is an algorithm that takes a formal description of a language
(e.g., a DFA) and tells whether or not some property holds.

1. Test for Membership: Decidable.


2. Test for Emptiness: Decidable
3. Test for finiteness: Decidable

Types of Turing Machines:


Turing machines (TM) can also be deterministic or non-deterministic, but this does not make them any more or less
powerful.
However, if the tape is restricted so that you can only see use of the part of the tape with the input, the TM becomes less
powerful (linear bounded automata) and can only recognise context sensitive languages.
Many other TM variations are equivalent to the original TM. This includes the following −

 Multi-track
 Multi-tape
 Multi-head
 Multi-dimensional tape
 The off-line Turing machine

Multi-tape Turing Machine


A Turing machine with several tapes we call it a multi tape Turing machine.
Every tape’s have their own Read/Write head
For N-tape Turing Machine
M={( Q,X, ∑,δ,q0,B,F)}
We define
δ=QxXN ->Q x XN x {L,R}N
Example
If n=2 with current configuration δ(q0,a,e)=(q1,X,Y,L,R)
δ=QxXN ->Q x XN x {L,R}N
Non Deterministic Turing Machine
It is similar to DTM except that for any input and current state it has a number of choices.
A string is accepted by a NDTM if there is a sequence of moves that leads to a final state
The Transition function −
=Q x X ->2QxXx(L,R) 
A NDTM is allowed to have more than one transition for a given tape symbol.

Multi-head Turing machine


It has a number of heads instead of one.
Each head independently reads/ writes symbols and moves left/right or keeps stationery.
Off-line Turing Machine
An offline Turing machine has two tapes, which are as follows −

 One tape is read-only and contains the input.


 The other is read-write and is initially blank.
1. Multiple track Turing Machine: 
 
 A k-track Turing machine(for some k>0) has k-tracks and one R/W head that reads and writes all of them one
by one.
 A k-track Turing Machine can be simulated by a single track Turing machine

2. Two-way infinite Tape Turing Machine: 


 
 Infinite tape of two-way infinite tape Turing machine is unbounded in both directions left and right.
 Two-way infinite tape Turing machine can be simulated by one-way infinite Turing machine(standard Turing
machine).

3. Multi-tape Turing Machine:


 It has multiple tapes and is controlled by a single head.
 The Multi-tape Turing machine is different from k-track Turing machine but expressive power is the same.
 Multi-tape Turing machine can be simulated by single-tape Turing machine.

4. Multi-tape Multi-head Turing Machine: 


 
 The multi-tape Turing machine has multiple tapes and multiple heads
 Each tape is controlled by a separate head
 Multi-Tape Multi-head Turing machine can be simulated by a standard Turing machine.
5. Multi-dimensional Tape Turing Machine: 
 
 It has multi-dimensional tape where the head can move in any direction that is left, right, up or down.
 Multi dimensional tape Turing machine can be simulated by one-dimensional Turing machine

6. Multi-head Turing Machine:


 A multi-head Turing machine contains two or more heads to read the symbols on the same tape.
 In one step all the heads sense the scanned symbols and move or write independently.
 Multi-head Turing machine can be simulated by a single head Turing machine

7. Non-deterministic Turing Machine: 


 
 A non-deterministic Turing machine has a single, one-way infinite tape.
 For a given state and input symbol has at least one choice to move (finite number of choices for the next
move), each choice has several choices of the path that it might follow for a given input string.
 A non-deterministic Turing machine is equivalent to the deterministic Turing machine.

 If there is a method to do anything, then it can be done by some turing


machine. This assumption is called as the Church Turing thesis or as Church's
hypothesis

UNDECIDABILITY:
The problems for which we can’t construct an algorithm that can answer the problem correctly in the infinite time are termed
as Undecidable Problems in the theory of computation (TOC).
A problem is undecidable if there is no Turing machine that will always halt an infinite amount of time to answer as
‘yes’ or ‘no’.
Examples
The examples of undecidable problems are explained below. Here, CFG refers to Context Free Grammar.
 Whether two CFG L and M equal − Since, we cannot determine all the strings of any CFG, we can predict that two
CFG are equal or not.
 Given a context-free language, there is no Turing machine (TM) that will always halt an infinite amount of time and
give an answer to whether language is ambiguous or not.
 Given two context-free languages, there is no Turing machine that will always halt an infinite amount of time and give
an answer whether two context-free languages are equal or not.
 Whether CFG will generate all possible strings of the input alphabet (∑*) is undecidable.

You might also like