Solution

The given DFA does not accept string “baab” hence the statement “the DFA accepts all strings having “baa” as substring” is false. The given DFA does not accept string “ba” hence the statements “the DFA accept all strings ending with “a” and “DFA accept all strings which do not end with “b” are false.

Solution

State q2 is unreachable so we can remove state q2. Now the NFA is

The NFA accepts {ϵ, a, aa, aaa, aaaa, ………..} i.e., L=a*

The min DFA is

Solution

A string is a finite sequence of symbol from ∑ , so a string can never be infinite. Since in regular expression we have “bb*”, so it is an infinite set.

Solution

S1 is false as every subset of Context free language need not be regular.

For example L={w | w ϵ{a,b}* & |w_a|=|w_b| } is CFL (i.e, no. of “a’s” in w equal to number of “b’s” in w) which is CFL and its subset L={anbn |n>0} is also CFL and not regular. S2 is true as any finite subset of any language is always regular and hence context free also.

Solution

The language is L={a^n b^k c^m | k=n+m & n,m >0}, also equivalent to L={a^n b^(n+m) c^m | n,m >0}.

The strings in L are {abbc, aabbbc, abbbcc, aabbbbcc, …………….}

The correct grammar is S→AB & A→aAb |ab & B→bBc |ab

Solution

We can use product automata.

L1= {every string begin with a} and the DFA for L1 is

L2={every string end with “b”} and the DFA for L2 is

Now the required language L= L1 U L2

The product automata will have six states {AD, AE, BD, BE, CD, CE}

The initial state will be AD and final state will be { AE, BD, BE,CE}. Please note in case of union of product automata if any state is final state then in product automata that state will be final state for example state AE is final state since E is final state but state AD is not a final state since both A and D are non-final state.

Since state AE is unreachable so we can remove this state. State BD and BE are equivalent hence they can be merged during minimization process.

Hence the min DFA will be

An easy approach to this problem: We can directly analyse the strings present in language and make the min DFA directly. L will contain all strings begin with “a” or end with “b” which means strings begin with “b” and end with “a” will not present in language.

Hence L will contain all strings

Case 1: if begin with “a” then can be end with anything “a” or “b”

Case 2: if begin with “b” then must be end with “b”.

Hence the min DFA will be

Solution

L = L1 ∩ L2 such that

L1= {every string second symbol from LHS is a}

L2= {every string is having odd length}

The DFA for L1 and L2 is

The product automata will have 8 states {→AE, AF, BE, BF, CE, *CF, DE, DF}

AE is initial state and CF is final state. Please note in case of intersection of product automata if both states are final state then only in product automata that state will be final state for example state CE is final state since C and E both are final states but states CE is not final state since both C and E are not final states. States AF and BE are unreachable states so not included in product automata.

States DF and DE are equivalent and hence can be merged. The min DFA for L is given below.

An easy approach to find min DFA of L is to analyse the strings in language and directly make the min DFA.

The language contains all strings where the second symbol from LHS is “a” so all strings must have length greater than equal to 2. Then all strings of odd length. So combinedly L is a language containing all strings of odd length greater than 2 (i.e, strings length will start from 3) and the second symbol from LHS is “a”. The strings in language will be

{aaa, aab,baa, bab, ……………….}

The min DFA will be

Solution

L1 is DCFL as push pop is clearly defined. First push “w” then all x’s. Pop each “x” for one “y” and then if x’s and y’s are over then pop each symbol of “w” from stack while matching with “wr”.

L2 is CFL but not DCFL, as we cannot find the middle of wwr. So push pop deterministically cannot be defined.

Solution

{a^n a^m b^n b^m | n,m > 0}= {a^(n+m) b^(n+m) | n,m > 0}

Both L1 and L2 are equivalent to

L={a^k b^k | k=n+m & n,m>0} Hence both are DCFL.

Solution

Solution

Solution

Assume string w=abc. The NFA which accept w is given below

The proper prefixes of “abc” are {a, ab}

The NFA which accept proper prefixes is given below

Hence for length 3 string min NFA require 4 states out of which 2 states are final. So for “n” length string we require min NFA with n+1 states and n-1 states will be final.

Solution

Since NPDA is more powerful than DPDA hence every language accepted by DPDA is also accepted by NPDA so S1 is true.

S2 is wrong, as L=a*b* is accepted by FA but its subset L1={a^nb^n | n>0} is not accepted by FA.

Solution

The Turing machine corresponding to recursively enumerable language will always halt for any string present in language and may or may not halt for string not in language.

The Turing machine corresponding to recursive languages will always halt Turing machine, i.e., TM for recursive language will always halt for any input.

Solution

The TM make X to first “a” and then skip all a’s and b’s and reach to P, there at end see the blank and change direct to left and make last “b” into “Y”, so in place of P=(β,β,L). Then again skip all b’s and a’s and reach to first blank at Q, then change direction into right, so at Q=(β,β,R)

Solution

Every NFA can be converted into DFA, hence we can convert NFA M1 and M2 into DFA D1 and D2. Now whether D1 and D2 are equivalent can be decided by if D1 intersection D2(complement) = φ. If D1 and D2 are equivalent the intersection of D1 and D2 complement will be empty. Hence P1 is decidable.

Similarly P2 is also decidable since we can convert any NFA into DFA and any regular expression into DFA. So we can compare whether both are equivalent or not.

Solution

Solution

The min NFA for given language will be

Solution

Solution

The given NFA accepts strings {ϵ,a,aa,aaa,aaaa,…………}

Please note NFA accept even length strings also. For example “aa”

(q1, ϵ) -> q4

(q4,ϵ) ->q2

(q2,a)->q3

(q3,a)->q4

(q4,ϵ) ->q2

Hence L(NFA)=a*

Solution

The strings in language are {ϵ, aa, aaaa, aaaaaa, ………, bb, bbbb,…….}

Solution

The given PDA accept all strings “w” which begin with “a” and all strings w such that no(w_a) = no(w_b) +1. The option “All strings “w” such that no(w_a) = no(w_b) +1” is not correct because PDA does not accept string “baa”

Solution

Solution

The given grammar is CFG but the language generated by grammar is regular.

The strings generated by grammar is {ϵ, aa, aaaa, ……, bb, bbbb, …, aabb, aabbbb, ………..}

L(G)= (aa)*(bb)*

Solution

Solution

L_A is regular as any string which begin and end with same symbol will belong to L_A.

L_B is also regular as L_B =(a+b)*. Since w ϵ{a,b}* , hence w can be empty string (ϵ) also. If w=ϵ and X ϵ {a,b}* means X=(a+b)*

So Xww^r is equivalent to (a+b)*.ϵ.ϵ = (a+b)*

Solution

Solution

L1=a* , L2=b* and L3=c* , all are regular languages

Now concatenation of L1, L2 and L3 must be regular, since regular languages are closed in concatenation.

So L=a*b*c* hence regular but infinite language.

Solution

The given TM accepts strings {a, aba, ababa, ……} hence the correct language is L={a(ba)^n | n>=0}

Solution

Any Turing machine by default accepts recursively enumerable languages.

From decidability table, we know that the emptiness problem and finiteness problem of recursively enumerable languages is undecidable. Hence both are undecidable.

Solution

From decidability table, we know that the completeness problem and regularity problem of recursively enumerable languages is undecidable. Hence both are undecidable.

Solution

The given TM accept only one string “a” hence the language accepted by TM is finite as well as regular. The TM will go to infinite loop if the input string is “ab”.

Solution