Solution

The given FA accepts strings { ϵ,a,aa,aaa, ……………..}

So language accepted by FA= a*

Now as we know for any regular expression R

RR*+ ϵ =R*

So aa*+ ϵ =a*

Hence the correct regular expression is (aa*+ϵ)

Solution

The minimal NFA is given below

Solution

The given FA accepts string “aab” so it does not accept the language containing all strings which start and end with the same symbol. Please note if language is “all strings which start and end with the same symbol” then FA must not accept any string which start and end with different symbol.

The given DFA is a minimal DFA. We can verify this by applying DFA minimization procedure.

A language is co-finite if the complement of language is finite. If we do the complement of DFA then also we find that the DFA (complemented) accepts infinite strings hence the given language is not co-finite as its complement is also infinite.

If A is also the final state then all states of this DFA will be final state and we know that if all states of a DFA are final state then DFA accepts universal language {𝝨* i.e, (a+b)*}.

Solution

Both are CFL as we can make NPDA, but we cannot make DPDA for L1 and L2 hence they are not DCFL.

Solution

L1 U L2 = { a^n b^n | n > 0} U { b^n a^n | n > 0}

We can make DPDA for this language hence it is DCFL.

The DPDA is given below

Solution

The concatenation of any language with empty language is an empty language, i.e, L.𝛟 = 𝛟 for any language L.

Hence if L is recursively enumerable also then also L.𝛟 = 𝛟 and 𝛟 (empty language) is regular hence it is recursive also. So P1 is trivially decidable (i.e, by default it is decidable).

As we know L U L(complement) = 𝝨* , for any language L. Hence if L is not recursively enumerable then also L U L(complement) = 𝝨* and 𝝨* (sigma*) is a regular language so it is recursive also. Hence P2 is also trivially decidable.

Solution

Since designated initial and final state is given so lets assume state A is initial state and state C is final state. Since DFA must accept empty language so state C must be unreachable in all cases.

Four cases are possible.

Case 1:

Case 2:

Case 3:

Case 4:

Total: 81+36+36+36189

Solution

L2 is a DCFL, we need to push all a’s and then pop two “a’s” for each “b”. Hence it is DCFL.

L1 is not CFL. Since k is not fixed so we cannot guess how many “a’s” need to pop for each “b”.

Solution

R1 is wrong as (a^+b^+ )^+ cannot generate strings which begin with “b” like {ba, bb, baba, …….} hence it cannot equal to (a*b*)* [Please note (a*b*)*=(a+b)*]

R2 is correct.

Solution

In language L every strings ends with “a”. Plz note that, ends with atleast “a” is same as end with “a”.

So L= (a+b)*a

If we apply DelEnd operation to L then =>

DelEnd(L) = (a+b)*

Hence to represent DelEnd(L) we require one state only and also DelEnd(L) is the superset of L.

Since DelEnd(L) is superset of L, hence, L ∩ DelEnd(L) = L

Solution

If L is a recursively enumerable then whether a given string belongs to L or not is undecidable. Hence, If L is a recursively enumerable language then α ϵ L and β L both are undecidable, (where α and β are any string from ∑).

Solution

The PDA accept the strings {aabc, aaabc, aaabcc, aaaabcc, aaaabccc, aaaabbcc,…….. } . Hence PDA accepts the L={ax by cz | x,y,z >0 & x>=(y+z)

Solution

FOLLOW(P) = FIRST(QR) ∪ FIRST(t)

FIRST(QR) = FIRST(qQR) ∪ FIRST(R) //when Q→∊

FIRST(R) = FIRST(Rr) ∪ FIRST(Qm) ∪ {∊}

⇒ {r} ∪ {q,m} ∪ {∊}

= {r,q,m,∊}

FOLLOW(P) = {t} ∪ FIRST(QR)

= {t} ∪ {q} ∪ FIRST{R}

= {t} ∪ {q} ∪ {r,q,m,∊}

= {t,q,r,m,∊}

When FIRST(QR) = ∊ then FOLLOW(P) = FOLLOW(S)

FOLLOW(S) = FIRST(PQR) ∪ {$}

= {P} ∪ {$} ∪ FIRST{QR} //when P→∊ then {PQR→QR}

= {P,$} //FIRST{QR} is already included in FOLLOW(P)

Hence FOLLOW(P) = {t,q,r,m} ∪ {p,$}

= {t,q,r,m,p,$}

Solution

The grammar can be written as

S → S+T | T*S | T

T → T % T | F

F → F − Z | Z

Z → id

Since + and * both derived by S so they have the same precedence. Operator + is left associative as S → S+T having left recursion and operator * is right associative as S → T*S is having right recursion.

% is having more precedence than + and * as it defined by T which is at next level to S. The associativity of % is not defined as T → T % T is having both left as well as right recursion.

Operator - is having highest precedence and it is left associative.

Solution

The grammar is ambiguous as string “xyy” has two parse trees.

Hence grammar is not LALR(1) as well as not LL(1), CLR(1).

Solution

The grammar is LR(0) hence it is SLR(1), LALR(1) and CLR(1). Since grammar is parsed by LR(0) parser hence it is unambiguous also.

The LR(0) canonical set of items are given below which shows no conflict in any state.

Solution

String: "pppqrr"

Solution

More CPU bound processes implies CPU has to be shared among many processes and hence makes it difficult to achieve multi-programming.

Solution

Shorter time slice leads to more context switches. Hence, context switch delay increases.

Solution

In LOOK the disk head looks ahead in its direction of movement for the last request. It moves to the last request and changes its preferred direction there without moving to the last cylinder and continues servicing the request in the other direction. Thus, it eliminates unnecessary seek operations and hence decreases the average response time and lowers the variance of response time

Solution

blocked state

Solution

Solution

Solution

Solution

Logical address 0001010010111010 implies VAS has 16bits. Since page has 256 words, last 8 bits are page offset. Given that frame number = pagenumber / 4 = 00010100 divided 0100 gives 00000101. Therefore physical address is 0000010110111011.

Solution

EMAT = hit(TLB+M) + (1-hit)(TLB+3M) = 0.95*(115)+0.05*(15+300) =125ns

Solution

In a JK flip-flop, the output will oscillate back and forth between 0 and 1 for the input J=K=1. This is due to feedback connections.

Solution

The output of an odd function is 1 iff the input has an odd number of 1s.

Let “n” is the number of inputs.

Case 1: If “n” is odd then, EX-OR = EX-NOR.

If the number of 1’s in the input to EX-OR or EX-NOR is odd, then output is 1.

Case 2: If “n” is even then EX-OR is a complement of EX-NOR.

If the number of 1’s in the input to EX-OR is odd, then output is 1.

So, the two input Ex-OR is also an odd function.

Solution

Solution

The equation for b_i is g_n ⊕g_n-1⊕ g_n-2 ⊕ ...⊕ g_i.

b_n=g_n

b_n-1 = g_n ⊕ g_n-1

b_n-2 = g_n ⊕ g_n-1 ⊕ g_n-2

b₀ = g_n ⊕g_n-1⊕ g_n-2 ⊕ ...⊕ g₀.

Solution

f(w,x,y,z)= w’+x+y’+wx’yz

= (w’+wx’yz) + x + y’

= w’ + x’yz + x + y’

= w’ + y’ + (x+x’yz)

= w’ + y’ + x + yz

= w’ + x + (y’+yz)

= w’ + x + y’ + z

Solution

Number of bits in ASCII code N= 7.

Let K is the number of bits to be attached.

2K ≥ N + K + 1.

K=4 satisfies the above equation.

Solution

The output of an odd function is 1 iff the input has an odd number of 1s.

Ex-OR with even number of inputs is also an odd function.

The input combinations which have odd numbers of 1s are 1, 2, 4, 7, 8, 11, 13, and 14.

So, f(A⊕B⊕C⊕D)= Σ(1,2,4,7,8,11,13,14)