# Theory of Computation Subject Wise UGC NET Question Analysis

Theory of Computation Subject Wise UGC NET Question Analysis

#### Show Answer With Best Explanation

Explanation:
Regular language does not have any memory to compare.
A. L={ (01)n0k | n > k, k>=0 }
Here, occurance of n is greater than occurance of k, for that we need to compare value of n with k, and regular language does not have power to compare. so,it is not regular language. It is Context Free Language.

B. L={ cnbkan+k | n >= 0, k>=0 }
Here, occurance of c is less than or equal to ocuurance of a and Finite Automata cannot do this comparison. So, it is not regular language . It is Context Free Language.

C. L={ 0n1k | n≠k }
Here, occurance of n is not equal to occurance of k, and this type of comparison cannot be done by Finite Automata.So, it is also not regular language . It is Context Free Language.

So, Option(III) is correct.

#### Show Answer With Best Explanation

Explanation:
Given,
pushdown automata M=({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2})
where,
{q0, q1, q2} = Finite state of states
{a, b} = Input alphabet
{a, b, z} = Stack alphabet
δ = Transition Function
q0 = Initial state
z = Bottom of the stack
{q2} = Final state
Let’s Draw pushdown automata for a given Transition function:

First, keep pushing any number of a’s and b’s in the stack , and then pop one a from stack on seeing input alphabet a and pop one b from stack on seeing input alpbabet b. Keep popping untill we reach end of string λ. when we reach end of string λ and Top of Stack is z, then go to final state.
Let’s take one string and analyze them
suppose string

Language generated by above push down automata (L)= {wwR | w Є {a, b}+}
So, Option(IV) is correct.

#### Show Answer With Best Explanation

Explanation:
Statement A: L3 =L1 ∩ L2
L1 = { 0n1n0m | n>=1, m>=1 }
= {010, 0100, 00110, 001100……………………}
L2 = { 0n1m0m | n>=1, m>=1 }
= {010, 0010, 01100, 001100…………………. }
L3 =L1 ∩ L2
= {010, 001100, 000111000…………………….}
= {0n1n0n | n>=1}
Statement A is correct.
Statement B: L1 and L2 are context free languages but L3 is not a context free language
L1 = { 0n1n0m | n>=1, m>=1 }
let’s draw push down automata for above language:
=1, m>=1 }”>
Language L2 is Context Free Language.

L3 = { 0n1n0n | n>=1}
Here, n times 0 followed by n times 1 followed by n times 0, this kind of comparison cannot be done by Push Down Automata. So, it is not Context Free Language. It is Context Sensitive Language.
Statement B is correct.

Statement C: L1 and L2 are not context free languages but L3 is a context free language
As statement B is correct, Statement C is obviously incorrect.

Statement D: L1 is a subset of L3
L1 = { 0n1n0m | n>=1, m>=1 }
= {010, 0100, 00110, 001100……………………}
L3 ={ 0n1n0n | n>=1}
= {010, 001100, 000111000…………………….}
As see, L1 is superset L3
Statement D is incorrect.
So, Option(IV) is correct.

#### Show Answer With Best Explanation

Explanation:
S-> XY
->0XY | 1XY | 0Y
->0XY0 | 0XY1 | 0X0 | 1XY0 | 1X0 | 0Y0 | 0Y1 | 00
->0XY0 | 0XY1 | 000 | 1XY0 | 100 | 000 | 001 | 00

Option(i): has at least one 1
This is incorrect, because one of the string of above language is 00 which don’t contain 1.

Option(ii): has no consecutive 0’s or 1’s
This is incorrect, because one of the string of above language is 100 which has consecutive 0’s.

Option(iii): should end with 0
This is incorrect, because one of the string of above language is 001 which ends with 1.

Option(iv): has at least two 0’s
This is correct. Because X and Y always end with 0, so string has atleast two 0’s.

#### Show Answer With Best Explanation

Answer: (Marks to all from UGC NET )

#### Show Answer With Best Explanation

Explanation:
Since, Regular Language doesn’t have memory .So, it doesn’t have capacity to hold anything.

In L1, in order to calculate aźZ we have to first calculate zz  & store the value in memory then need to calculate power of a. but we already known that Regular Language doesn’t have capacity to hold anything. So, L1 is not regular language.

In L2, again we have to calculate zź , then store it & then need to find power of a. So, L2 is also not regular language.

In L3, we have to compare first ω with second ω. But, Regular Language doesn’t have capacity to compare two string. So L3 is also not regular language.

Theory of Computation Subject Wise UGC NET Question Analysis

#### Show Answer With Best Explanation

Explanation:
R = {a, ab, aa, aba, aaa, aab, abb…….}
S = {a, aa, ab, aab, aaa, abb, aba…….}
T = {ab, aab, aaab, …………………………}
If you notice then r ⊇ s ⊇ t

#### Show Answer With Best Explanation

Theory of Computation Subject Wise UGC NET Question Analysis