Solution

Complement of non-regular language can never be regular language. Since regular is closed under complement, so if complement is regular then complement of complement must be regular.

Assume L= non-regular and if L’= regular. Then (L’)’ = L = regular. But L is already given as non-regular. Hence if L is non-regular then L’ must be non-regular.

Union of two non-regular languages can be a regular language also. For example if L and L(complement) both are non regular. Then the union of them i.e,

L U L (complement)= ∑* which is a regular language.

Union of regular and non-regular language can be a regular language also. For example, let L is a non regular language and another language R is ∑*

Then L U R = ∑* as ∑* is the superset of any language L. Hence L (non-regular) U R (Regular) can be regular also.

Intersection of regular and non-regular language can be a non-regular language. For example let L is a non regular language and another language R is ∑*

Then L ∩ R = L as ∑* is the superset of any language L. Hence L (non-regular) ∩ R (Regular) = L can be non-regular also.

Solution

If S is the only final state then FA accepts only one string (empty string). If F is the only final state then FA accepts (0+1)*. Hence the statement, language accepted by FA will be (0+1)* if and only if S and F both are final states is a false statement.

Solution

Since |w|=2 hence w can be {aa, ab, ba, bb}

L will contain only 4 strings {aaaa, abba, baab, bbbb}

The minimal DFA will be

Solution

Transition table of NFA (without ϵ move)

The NFA will be

Hence NFA (without ∊) will be

Solution

Solution

Regular expression for odd number of a’s = a(aa)*

Now (L*)* = (a (aa)*)* = a*

The reason is in (a(aa)*)* if we suppose (aa)*=ϵ then (L*)*= a*

Now a* generates every string over ∑=a hence (a(aa)*)* also generate the same set of strings.

Solution

The regular expression generate all strings which has odd number of a’s followed by any number of b’s (greater than zero)

Plz note: (bb*)* = b* (as in bb* if b*=epsilon then (bb*)* = b*) and hence (bb*)*b = b*b

hence R is equivalent to

R: a(aa)*b*b

Solution

We can make FA from grammar

The grammar generates strings {ϵ, a, aa, …., ba, bba, bbba, ….bbaa,..., aba, …} hence S and A are final states.

Now minimise the DFA. State S and A are equivalent and hence will be merged, the minimal DFA will be

Solution

Solution

The equivalence of DCFL and regular is a decidable problem. Hence S1 is true but S2 is a false statement, as NFA can be converted into DFA and hence NFA and DPDA equivalence is also decidable.

Solution

Follow(S)= First(B) = {b}

In production A-> SB

When B->ϵ, then it is equivalent to A->S

Then follow(S)= follow(A) ={a}

By default follow(S)= {$}

So combinedly follow(S)={$,a,b}

Solution

The given grammar is not LL(1) as productions

A-> d and A->SB will go in the same cell of LL(1) parsing table.

The given grammar is not LR(0) as the production B → ϵ will cause shift -reduce conflict in state I₁.

But the given grammar is SLR(1) as B → ϵ will go in follow(B)= {a} only, so there will not be any SR conflict.

Hence this grammar is LALR(1) also.

Solution

int₁ main₂ (₃void₄)₅

{₆

int₇ num_val₈ =₉ 2₁₀ ;₁₁

num_val₁₂ *=₁₃ 5₁₄ ;₁₅

printf₁₆(₁₇ “\n Output %d \n”₁₈ ,₁₉ num_val₂₀++₂₁)₂₂ ;₂₃

return₂₄ 0₂₅ ;₂₆

}₂₇

Solution

Since SDT count the number of zeros and number of ones, hence the SDT is:

N→L {N.c=L.c}

L→L₁ B {L.c=L₁.c+B.c}

L→B {L.c=B.c}

B→0 { B.c =1}

B→1 { B.c =1}

Solution

Moving (x/y) outside the loop is code motion and reducing the number of iterations of loop (i+=2) is loop unrolling.

Solution

Replacing a costlier operation (*) by a cheaper one (+) is strength reduction.

Solution

(a* +bb*a*)* bb* == ((ϵ +bb*) a*)* bb*

(b*a*)* bb* // as (ϵ +bb*) = b*

(a+b)*bb* //as (b*a*)* = (a+b)*

(a+b)* b // as bb* will generate at least one “b” at end and (a+b)* will generate all strings (which has any number of b’s at end)

Now,

(a+b)(a+b)*b + b = = ( (a+b)(a+b)* + ϵ ) b

(a+b)* b // As (RR* + ϵ ) = R*

Hence all are equivalent.

Solution

Assume three states are {A,B,C}. Assume A is designated initial state and C is designated final state.

Since language is empty, so state C must be unreachable from initial state.

Four cases are possible.

Case 1: States B and C are unreachable from the initial state A.

Case 2: A is going to state B from a,b and state C is not reachable from state A and B.

Case 3: A is going to state A from “a” and to state B from “b” and state C is not reachable from state A and B.

Case 4: A is going to state B from “a” and to state A from “b” and state C is not reachable from state A and B.

Case 1:

Case 2:

Case 3:

Case 4:

Case 4:

Total: 81 + 36 + 36 + 36 = 189

Solution

Solution

FA accepts string “abb” hence it accepts all strings which start and end with the same symbol, is the wrong option. FA accepts string “aba” & “bab” hence it accepts all strings which do not end with “ab” or “ba”, is the wrong option.

The regular expression a(a+ba)* + b(b+ab)* does not generate string “abb” which is accepted by FA, hence this regular expression representing the language accepted by FA, is the wrong option.

Solution

L₁ is CFL but not DCFL. The PDA is given below.

L₂ is DCFL but not regular. In L2 the number of a's is equal to the number of b’s and the number of c’s equal to the number of d’s. The DPDA is given below.

Solution

L1 is regular as it is equivalent to L= (aa)*, as if w= an for any “n” then the string in L1 will be ww= a^n a^n = a^2n which is an even number of “a’s”.

L2 is CFL, as we need to push all a’s in stack before X and then pop one “a” from stack for each “a” after “X”. If at end stack is empty and input is over then accept otherwise reject the string. L2 will have strings {aXa, aaXaa, aaaXaaa, …………….}. Please X is a symbol outside of the alphabet.

Solution

Solution

Both L1 and L2 is equivalent to language L=a*b*c* hence both are regular. Any string of a*b*c* will be present in L1 and L2.

Solution

The given problem P is the State entry problem. We can prove problem P undecidable by reducing halting problem into problem P. We can argue that, since we can reduce the halting problem into the state entry problem and if the state entry problem is decidable then the halting problem will also be decidable, but since we already know that the halting problem is undecidable, hence state entry problem is also undecidable.

Problem P is Turing recognizable (recursively enumerable) but not Turing decidable (recursive).

State entry problem says that whether the TM “M” on string “w” visits state “q”. We already know that the halting problem is recursively enumerable but not recursive. We can convert the state entry problem into the halting problem by arguing that state “q” is halt state (final state) and hence state entry problem will be whether the TM “M” on string “w” visits (reaches) state “q_f” (halt state). It is equivalent to halting problem “whether TM “M” on input “w” halts (reach to halt state). Hence the state entry problem is Turing recognizable (recursively enumerable) but not Turing decidable (recursive) as it can be converted into the halting problem. Please note, if problem A is reducible to problem B then if A is undecidable then B is undecidable and if B is decidable (or semi decidable) then A is decidable (semi decidable).

Hence in order to prove P undecidable, we have to reduce the halting problem into problem P and in order to prove P semidecidable, we have to reduce problem P into halting problem.

Solution

Counting steps in a Turing machine is always decidable. It is because, we have to see only upto steps 2021 and after that what happens is not required. So it is always a halting process. Hence P1 is decidable. We have to run the Turing machine on some input, it will either halt before 2021 steps or take 2021 steps to process the string, so the Turing machine can decide whether it is taking 2021 steps or not.

P2 is undecidable. It is equivalent to the halting problem. Whether a Turing machine accept string “w” is undecidable, so acceptance of string of length 2021 is also undecidable.

Solution

From parse tree, we can conclude the grammar as:

E-> E+E | E*E| id

In this grammar + and * has equal priority, hence none of these is correct.

Solution

The grammar has left factoring [S→ ( X) & S→ ( t)], hence it is not LL(1). The grammar does not have indirect left recursion.

Please note: S→Sa is direct left recursion and S→ Aa & A→ S is indirect left recursion.

Follow(S)= Follow(X) [Because of production X→S] U { $ }

Follow(X)= { ) }

So Follow(S)= { ), $ }

The grammar is LR(0), hence SLR(1) as well as LALR(1).

If grammar is SLR(1) then it is also LALR(1) and both will have the same number of states.

Solution

The grammar is not LL(1), as the productions S contains left factoring (S→xAw & S→xBe)

The grammar is CLR(1) but not LALR(1). If we merge states I₁₂ and I₁₃ then there will be RR (reduce -reduce) conflict, hence it is not LALR(1) and hence not SLR(1) also.

Solution

Solution

The expression is (a-b)+c*(d+e)

Assume registers R1, R2 &R3

R1=a

R2=b

R1=R1-R2 // a-b

R2=d

R3=e

R2=R2+R3 // d+e

R3=c

R2=R3*R2 //c*(d+e)

R1=R1+R2 // (a-b)+c*(d+e)

Solution

Since it is asked for the minimum number of nodes and edges, we can assume that algebraic simplification (elimination of common subexpressions) is allowed.

The minimum DAG is

a0=b+c0

c1=a0+d0

f=a0+b

d1=f-b=a0+b-b=a0

e=c1-d1=a0+d0-d1=a0+d0-a0=d0

a1=e+b= d0+b

nodes=7

edges=8

Solution