TOC Question Bank Solution 2080-NEW

Differentiate Kleen closure from positive closure. Compute positive and Kleen closure of {ab}.

Kleen closure	Positiv Closure
The set of all the strings over an alphabet Σ with length ‘zero’ i.e empty string is called Kleen closure.	The set of all the strings over an alphabet Σ except empty string is considered as positive closure.
It is denoted by Σ *.	It is denoted by Σ +.
It is calculated as Σ* = Σ0 U Σ1 U Σ2 U Σ3	It is calculated as Σ+ = Σ1 U Σ2 U Σ3

for given alphabet Σ = {a, b}

kleen closure (Σ^*) = Σ⁰ U Σ¹ U Σ² U Σ³

={Φ} U {a , b} U {ab, ba, aa, bb} U ……….

Positive  closure (Σ⁺) = Σ¹ U Σ² U Σ³

={a , b} U {ab, ba, aa, bb} U ……….

Construct a PDA that accepts string over Σ ={a,b} that contains equal number of a’s followed by equal number of b’s. Show acceptance of aabb and aab.

This language accepts L = {ε, ab, aabb, aaabbb, ……………………….. }

Here, in this example, the number of ‘a’ and ‘b’ have to be same.

• Initially we put a special symbol ‘$’ into the empty stack.
• Then at state q₂, if we encounter input 0 and top is Null, we push 0 into stack. This may iterate. And if we encounter input 1 and top is 0, we pop this 0.
• Then at state q₃, if we encounter input 1 and top is 0, we pop this 0. This may also iterate. And if we encounter input 1 and top is 0, we pop the top element.
• If the special symbol ‘$’ is encountered at top of the stack, it is popped out and it finally goes to the accepting state q₄.

 

What is intractability? Define time and space complexity of turing machine.

Intractability is a technique for solving problems not to be solvable in polynomial time. The problem that can be solved within a reasonable time and space constraints is called tractable.

Time and Space Complexity of a Turing Machine

For a Turing machine, the time complexity refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written.

Time complexity all reasonable functions −

T(n) = O(n log n)

TM’s space complexity −

S(n) = O(n)

How conversion of PDA to CFG done ? Illustrate with example.

Construct regular expression over {1,2,….9} that represents

1. strings of even numbers with length 4 starting with 2 and ending with 8.
2. strings starting with odd numbers and ending with even numbers.

 

a.

2 + (2U4U6U8) + (2U4U6U8) + 8

b.
(1U3U5U7U9)⁺ + (2U4U6U8)⁺

Describe how multi-stack TM is different from the semi-infinite tape TM?

Multi-stack TM	semi-infinite tape TM
It has multiple stacks (typically two or more), each of which operates independently like a standard stack data structure.	It has a single tape that extends infinitely in one direction (usually to the right).
It can push symbols onto and pop symbols off of each stack independently.	The tape provides a linear, sequential storage mechanism, unlike the independent stacks of a multi-stack TM.
With multiple stacks, it can manage more complex computations efficiently, particularly tasks that benefit from parallel stack operations.	It is equivalent in computational power to the standard single-tape Turing Machine.
Useful for problems that involve nested structures or require efficient management of multiple independent data structures simultaneously (e.g., parsing nested expressions, simulating recursive function calls).	Commonly used in theoretical computer science to explore fundamental questions about computability and complexity, though its practical applications are more limited compared to multi-stack TMs.

 

Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram , over  {0, 1} that accept the string having substring 01 and ends with 1. Show the acceptance of 0111.

The extended transition function is a function that takes a state q and a string of input symbol w and returns the set of states. In DFA it returns a single state but NFA can return multiple states.

for example:

Now computing for δ^{^}(q₀, 01101)

solution:

 δ^{^}(q₀, 01101)

 δ^{^}(q₀, ε) = {q₀}

δ^{^}(q₀, 0) = {q_0, q₁}

δ^{^}(q₀, 01) = δ{q_0, 1} U δ{q_1, 1} = {q₀} U {q₁} = {q₀, q₁}

δ^{^}(q₀, 011) = δ{q_0, 1} U δ{q_2, 1} = {q₀} U {Φ} = {q₀}

δ^{^}(q₀, 0110) = δ{q_0, 0} = {q₀, q₁}

δ^{^}(q₀, 01101) = δ{q_0, 1} U δ{q_1, 1}

= {q₀} U {q₁}

= {q₀, q₁}

= Accepted.

For other part,

let w=w’ where w’ is the string having substring 01 and ends with 1.

for NFA first we need to fulfill the basic condition so basic NFA will be as:

The above fig show the basic NFA where the string has substring 01. Now for NFA which also ends with 1 will be as:

now,

transition table will be as:

for string o111 we need to show this as

δ(q_0, 0111)

= δ (δ(q_0, 0), 111)

= δ(δ(δ(q_0, 0), 1),11)

= δ(δ(δ(δ(q_0, 0), 1), 1), 1)

=

 

Define CFG. Construct a CFG that generates the language of all palindromes over {a,b} that do not contain the substring aa. Show the leftmost derevation and construct the equivalent parse tree for string babbbab.

A grammar is said to be context free if every rule has a non-terminal on the LHS. A context free grammar is a set of recursive rules used to generate patterns of strings.

A grammar G = (V, T, P, S) is said to be context free grammar where,

V = Finite set of non-terminal .

T = Finite set of terminals.

S = Starting symbol.

P = Production rule.

To construct a Context free grammar that generates the language of all palindromes over {a, b} that do not contain the substring “aa”, as follow:

V = {S, A}

T = {a, b}

S = {S}

P will be as,

A→aAa|bAb|a|b|ε

S→a|b|A|ε

Hence, it is the required grammar for the palindrome. we need to ensure that the aa is not the substring of the string formed.

now, for string babbbab

S→A

S→bAb                               ( A→bAb )

S→baAab                           ( A→aAa )

S→babAbab                       ( A→bAb )

S→babbbab                        ( A→b )

 

 

 

How Turing Machine is used as a computing function? Construct a TM for simulating a function f(x) = 2x for x = {1}. Itetrate the TM for input 11 and generate the output 1111.

Turing machine is a theoratical model which can be considered as a finite control machine connected to R/W head. It contain:

1. A finite control.
2. An input tape that is divided into cells.
3. Tape head that scan one cell at a time.

It is considered as a computing function as it can define a set of rules that describe how it processes input symbol and moves on its tape. It operates in discrete steps and can computefunctions through state transitions and tape manipulation, following the principles of algorithmic computation.

Let, a Turing Machine be T then,

T = (Q, Σ, ¬, δ, q₀, B, f) where,

Q = {q₀ , q₁ , q₂ , q₃ }

Σ = {1}

q₀ = {q₀ }

and now

δ(q₀, 1) = (q₁, 1, R)

δ(q₁, 1) = (q₂, 1, R)

δ(q₂, B) = (q₃, 1, R)

δ(q₃, B) = (q₃, 1, R)

δ(q₃, B) = (q₀, B, L)

itetrating the TM for input 11 and outpot 1111

for input 11 starting with q₀

δ(q₀, 1) = (q₁, 1, R)

δ(q₁, 1) = (q₂, 1, R)

δ(q₂, B) = (q₃, 1, R)

δ(q₃, B) = (q₃, 1, R)

hence, the output 1111 is obtained.

 

Prove that th language L ={aⁿ bⁿ cⁿ | n≥0} is not a context free grammar.

Let us consider that L is context free then by pumping lemma we know that there exist a pumping length ‘p’ such that

string S ≤ p

Here, let us represent the language as

a^p b^2p c^p

consider the value of power a and c are same

S = xyz

m = l+n

the breaking of a^p b^2p c^p in terms of xyz such that

|xy|≤p

|y|≥0

now,

x = a^l

y = a^m

z = b^2p c^p

then,

l+m = p

now, for checking xyⁱz then let us pump y by 2. so, i=2

xy²z = a^l (a^m)² b^2p c^p 

= a^l a^m a^m  b^2p c^p 

= a^l+m  b^2p c^p a^m

= a^p  b^2p c^p a^m  ∉ L

hence, L is not a context free.

State Arden’s theorem. Convert following DFA into its regular expression using Arden theorem.

This method is used to find regular expression recognized by a transaction system. According to Arden’s theorem for regular expression P and Q over alphabets if P doesn’t contain any empty string then

R = Q + RP have a unique solution R = QP*

Let us write equation for each state

Q₁ = Q₁0 + Q₃0

Q₂ = Q₁1 + Q₂1 +Q₃1

Q₃ = Q₃0

As we need to solve for the final state so,

Q₁ = Q₃0 + Q₁0

compearing it with R = Q + RP so,

R = Q₁

Q = Q₃0

P = 0

Now we can write,

Q₁ = Q₃0 0*

Design a Melay machine over {a, b} that generates output ‘A’ if the input string ends with aa else output ‘B’ if the string ends with bb.

false