ATC_MODULE 4&MODULE5 internal solutions

1) a. If L₁ and L₂ are context free languages then show that L₁ U L₂, L₁ - L₂, L₁ ꓵ L₂ are closed or not.

i)                    L₁ U L₂  

If L₁ and L₂ are context free languages then there exists a context-free grammar  G₁ = (V₁,Σ₁, R₁,S₁) and G₂ = (V₂,Σ₂,R₂,S₂) such that L₁=L(G₁) and L₂=L(G₂).

We will build a new grammar G such that L(G)=L(G₁) U L(G₂). G will contain all the rules of both G₁ and G₂.

 We add to G a new start symbol S and two new rules. S→S₁ and S→S₂. The two new rules allow G to generate a string iff at least one of G₁or G₂ generates it.

So, G = ( V₁ U V₂ U {S}, Σ₁ U Σ₂, R₁ U R₂ U {S→ S₁,S→S₂}, S )

Therefore, the context-free languages are closed under union

ii)                  L₁ - L₂

Given language L₁ , ￢L₁=Σ*- L₁ and L₂ , ￢L₂=Σ*- L₂

Σ* is context-free So, if the context-free languages were closed under difference, the complement of any CFL would necessarily be context-free But we just showed that is not so.

Therefore, L₁ – L₂ does not satisfies properties of context-free and the context-free languages are not closed under difference.

iii)                L₁ ꓵ L₂

Let: L₁={aⁿ bⁿ c^m | n, m ≥ 0} L₂={a^m bⁿ cⁿ | n, m ≥ 0} Both L₁and L₂ are context-free since there exist straight forward CFGs for them.

But now consider: L =L₁∩L₂ ={aⁿ bⁿ cⁿ | n, m ≥ 0}. If the context-free languages were closure under intersection. L would have to be context-free. But we have proved that L is not CFG by using pumping lemma for CFLs.

Therefore, the context-free languages are not closed under intersection.

1) b. Define Pumping Theorem in CFL. Show that aⁿ bⁿ cⁿ is not context free.

Statement: If L is CFL, then: ∃k ≥ 1 (∀strings w ∈ L, where |w| ≥ k (∃ u,v,x,y,z (w=uvxyz, vy ≠ Ɛ, |vxy| ≤ k and ∀q ≥ 0 (u v ^qx y^q z is in L)))).

L = { aⁿ bⁿ cⁿ  | n>=0} is Not Context-Free.

Solution: If L is CFL then there would exist some k such that any string w, where |w|>=k must satisfy the conditions of the theorem.

Let w = a^kb^kc^k, where ‘k’ is the constant from the Pumping lemma theorem. For w to satisfy

the conditions of the Pumping Theorem there must be some u,v,x,y and z, such that w=uvxyz, vy≠Ɛ, |vxy|≤k and ∀q ≥ 0 , uv^qxy^qz is in L.

w = aaa…aaabbb…bbbccc…ccc, select v=aabbb & y=ccc:

Let q=2, then v² and y² will result following in w

w=aaa…aaabbaabb b..bbccccc…ccc

The resulting string will have letters out of order and thus not in L.

So L is not context-free.

2) a. Explain Turing Machine Model.

The Turing machine can be thought of as finite control connected to a R/W (read/write) head. It has one tape which is divided into a number of cells. The block diagram of the basic model for the Turing machine is given in Fig.

Turing machine model

 

Each cell can store only one symbol. The input to and the output from the finite state automaton are affected by the R/W head which can examine one cell at a time. In one move, the machine examines the present symbol under the R/W head on the tape and the present state of an automaton to determine:

(i) A new symbol to be written on the tape in the cell under the R/W head,

(ii) A motion of the R/W head along the tape: either the head moves one cell left (L), or one cell right (R).

(iii) The next state of the automaton, and

(iv) whether to halt or not.

Definition: Turing machine M is a 7-tuple, namely (Q, Σ, Г, ẟ, q₀, b, F), where

1. Q is a finite nonempty set of states.

2. Г is a finite nonempty set of tape symbols,

3. b ∈ Г is the blank.

4. Σ is a nonempty set of input symbols and is a subset of Г and b ∉ Σ.

5. ẟ is the transition function mapping (q, x) onto (q', y, D) where D denotes the direction of movement of R/W head; D=L or R according as the movement is to the left or right.

6. q₀ ∈ Q is the initial state, and

7. F ⊆ Q is the set of final states.

2) b. Construct a Turing Machine for aⁿ bⁿ cⁿ : n>=1.

 

 

Part B

3. Write a short note on the following

            i. Multi Tape Turing Machine

            ii. Post Correspondence Problem

i.                    Multi Tape Turing Machine

A multi tape TM has a finite set Q of states, an initial state q₀, a subset F of Q called the set of final states, a set P of tape symbols, a new symbol b, not in P called the blank symbol.

There are k tapes, each divided into cells. The first tape holds the input string w. Initially, all the other tapes hold the blank symbol.          

Initially the head of the first tape (input tape) is at the left end of the input w. All the other heads can be placed at any cell initially.

ẟ is a partial function from Q x Г^k  into Q x Г^k  x {L, R, S}^k. We use implementation description to define ẟ. Figure represents a multi tape TM. A move depends on the current state and k tape symbols under k tape heads.

Fig: Multi tape Turing Machine

In a typical move:

(i) M enters a new state.

(ii) On each tape, a new symbol is written in the cell under the head.

(iii) Each tape head moves to the left or right or remains stationary. The heads move         independently some move to the left, some to the right and the remaining heads do not move.

            The initial ID has the initial state q₀, the input string w in the first tape (input tape), empty strings of b's in the remaining k - 1 tapes. An accepting ID has a final state, some strings in each of the k tapes. 

ii.                  Post Correspondence Problem

The Post Correspondence Problem (PCP) was first introduced by Emil Post in 1946. Later, the problem was found to have many applications in the theory of formal languages. The problem over an alphabet ∑ belongs to a class of yes/no problems and is stated as follows: Consider the two lists x = (x₁  . . . x_n), y = (y₁ . . . y_n) of nonempty strings over an alphabet ∑ = {0, 1}. The PCP is to determine whether or not there exist i₁, . . . , i_m where 1 ≤  i_j  ≤ n, such that

x_i1  . . . x_{im =} y_i1 . . . y_im

Note: The indices i_j's need not be distinct and m may be greater than n. Also, if there exists a solution to PCP, there exist infinitely many solutions.

Example:

Does the PCP with two lists x = (b, bab³, ba) and y = (b³, ba, a) have a solution?

Solution:

We have to determine whether or not there exists a sequence of substrings of x such that the string formed by this sequence and the string formed by the sequence of corresponding substrings of yare identical. The required sequence is given by i₁ =2,

i₂ = 1, i₃ = 1, i₄ = 3, i.e. (2, 1, 1, 3), and m =4. The corresponding strings are

 

Thus PCP has a solution.

4. Write a short note on the following:

            i. Linear Bounded Automata

            ii. Halting Problem of TM

iii. Growth rate of function

i.                    Linear Bounded Automata (LBA)

LBA important because (a) the set of context-sensitive languages is accepted by the model, and (b) the infinite storage is restricted in size but not in accessibility to the storage in comparison with the Turing machine model. It is called the linear bounded automaton (LBA) because a linear function is used to restrict (to bound) the length of the tape.

      A linear bounded automaton is a nondeterministic Turing machine which has a single tape whose length is not infinite but bounded by a linear function of the length of the input string. The models can be described formally by the following set format:

M = (Q, ∑ , Г , ẟ, q₀ , b , ₵ , $, F )

All the symbols have the same meaning as in the basic model of Turing machines with the difference that the input alphabet L contains two special symbols ₵ and $. ₵ is called the left-end marker which is entered in the leftmost cell of the input tape and prevents the R/W head from getting off the left end of the tape. $ is called the right-end marker which is entered in the rightmost cell of the input tape and prevents the R/W head from getting off the right end of the tape. Both the end markers should not appear on any other cell within the input tape, and the R/W head should not print any other symbol over both the end markers.

ii.                  Halting Problem of TM

Consider a problem A is reducible to problem B if a solution to problem B can be used to solve problem A.

For example, if A is the problem of finding some root of x⁴- 3x² + 2 = 0 and B is the problem of finding some root of x²-2 = 0, then A is reducible to B. As x²-2 = 0 is a factor of x⁴- 3x² + 2 = 0  a root of x²-2 = 0 is also a root of x⁴- 3x² + 2 = 0.

Theorem:  HALT_TM = {(M, w) | The Turing machine M halts on input w} is undecidable.

Proof:  We assume that HALT_TM is decidable, and get a contradiction. Let M₁ be the TM such that T(M₁) = HALT_TM and let M₁ halt eventually on all (M, w). We construct a TM M₂ as follows:

1. For M₂, (M, w) is an input.

2. The TM M₁ acts on (M, w).

3. If M₁ rejects (M, w) then M₂ rejects (M, w).

4. If M₁ accepts (M, w), simulate the TM M on the input string w until M halts.

5. If M has accepted w, M₂ accepts (M, w); otherwise M₂ rejects (M, w).

    When M₁ accepts (M, w) (in step 4), the Turing machine M  halts on w. In this case either an accepting state q or a state q' such that ẟ(q', a) is undefined till some symbol a in w is reached. In the first case (the first alternative of step 5) M₂ accepts (M. w).

In the second case (the second alternative of step 5) M₂ rejects (M, w).

It follows from the definition of M₂ that M₂ halts eventually.

Also, T(M₂) = {(M, w) | The Turing machine accepts w}

  = A_TM

This is a contradiction since A_TM is undecidable.

iii.                Growth rate of function Definition with example

Definition: Let f, g : N → R⁺ (R⁺ being the set of all positive real numbers). We say that f(n) = O(g(n)) if there exist positive integers C and N₀ such that

f(n) ≤ Cg(n) for all n ≥ N₀ .

In this case we say f is of the order of g (or f is 'big oh' of g)

Note: f(n) = O(g(n)) is not an equation. It expresses a relation between two functions f and g.

Example:

      Let f(n) = 4n³ + 5n² + 7n + 3. Prove that f(n) = O(n³).

Solution:

      In order to prove that f(n) = O(n³) take C =5 and N₀ = 10. Then

f(n) =4n³ + 5n² + 7n + 3 ≤ 5n³       for    n ≥10

When n = 10, 5n² + 7n + 3 =573 < 10³.  For n > 10, 5n² + 7n + 3 < n³

Then, f(n) = O(n³).

• References:
• Elaine Rich,  Automata, Computability and Complexity, 1st  Edition, Pearson Education,2012/2013
• K L P Mishra, N Chandrasekaran , 3rd Edition, Theory of Computer Science, PhI, 2012.