Theory of Computation Subject Wise UGC NET Question Analysis
Theory of Computation Subject Wise UGC NET Question Analysis
Q1➡| NET June 2021 Which of the following languages are not regular? A. L={ (01)n0k | n > k, k>=0 } B. L={ cnbkan+k | n >= 0, k>=0 } C. L={ 0n1k | n≠k } Choose the correct answer from the options given below:
i ➥A and C only
ii ➥ A and B only
iii ➥A, B and C
iv ➥B and C only
Show Answer With Best Explanation
Answer: III 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.
Q2➡| NET June 2021 What language is accepted by the pushdown automaton M=({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) with δ(q0, a, a) ={ (q0, aa) }; δ(q0, b, a) ={(q0, ba)} δ(q0, a, b) ={ (q0, ab) }; δ(q0, b, b) ={ (q0, bb) } δ(q0, a, z) ={ (q0, az) }; δ(q0, b, z) ={ (q0, bz) } δ(q0, λ, b) ={ (q1, b) }; δ(q0, λ, a) ={ (q1, a) } δ(q1, a, a) ={ (q1, λ) }; δ(q1, b, b) ={ (q1, λ) } δ(q1, λ, z) ={ (q2, z) }?
i ➥L = { w | na(w) <= nb(w), w Є {a, b}+}}
ii ➥ L = { w | na(w) = nb(w), w Є {a, b}+}}
iii ➥L = { w | nb(w) <= na(w), w Є {a, b}+}}
iv ➥L= {wwR | w Є {a, b}+}
Show Answer With Best Explanation
Answer: IV 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 oneb 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.
Q3➡| NET June 2021 L1 = { 0n1n0m | n>=1, m>=1 } L2= { 0n1m0m | n>=1, m>=1 } L3 = { 0n1n0n | n>=1} Which of the following are correct statements? A. L3 =L1 ∩ L2 B. L1 and L2 are context free languages but L3 is not a context free language C. L1 and L2 are not context free languages but L3 is a context free language D. L1 is a subset of L3 Choose the correct answer from the options given below:
i ➥A and C only
ii ➥ A and D only
iii ➥A only
iv ➥ A and B only
Show Answer With Best Explanation
Answer: IV 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.
Q7➡| NET June 2021 Given below are two statements Statement I: The family of context free languages is closed under homomorphism Statement II: The family of context free languages is closed under reversal. In light of the above statements, choose the correct answer from the options given below
i ➥Both Statement I and Statement II are false
ii ➥ Both Statement I and Statement II are true
iii ➥Statement I is false but Statement II is true
Q10➡| NET November 2020 Consider the following languages:
i ➥ L1 and L2 only
ii ➥ L1 and L3 only
iii ➥L1 only
iv ➥ None of these
Show Answer With Best Explanation
Answer: IV 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
Q11➡|NET November 2020 Consider the following regular expressions: a) r=a(b+a)* b) s=a(a+b)* c) t=aa*b Choose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above:
i ➥ L(r)⊆L(s)⊆L(t)
ii ➥ L(r)⊇L(s)⊇L(t)
iii ➥ L(r)⊇L(t)⊇L(s)
iv ➥ L(s)⊇L(t)⊇L(r)
Show Answer With Best Explanation
Answer: II 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
Q12➡|NET November 2020 Let L1 and L2 be languages over Σ =(a,b) represented by the regular expressions (a* + b)* and (a+b)* respectively. Which of the following is true with respect to the two languages?
Q13➡| NET November 2020 Which of the following grammars is (are) ambiguous? (A) s → ss | asb | bsa | λ (B) s → asbs | bsas | λ (C) s → aAB A → bBb B → A | λ where λ denotes empty string Choose the correct answer from the options given below:
Q16➡|NET November 2020 Given below are two statements: Statement I: The problem “Is L1 ∧ L2=Ø?” is undecidable for context sensitive languages L1 and L2. Statement II: The problem “Is W ∈ L?”is decidable for context sensitive language L, (where W is a string). In the light of the above statements, choose the correct answer from the options given below:
i ➥ Both Statement I and Statement II are true
ii ➥ Both Statement I and Statement II are false
iii ➥Statement I is correct but Statement II is false
iv ➥Statement I is incorrect but Statement II is true
Q17➡|NET November 2020 Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language. Consider the following problems: A) Is L(G1)=L(G2)? B) Is L(G2)≤L(G1)? C) Is L(G1)=R? Which of the problems are undecidable?
Choose the correct answer from the options given below:
Theory of Computation Subject Wise UGC NET Question Analysis
Q18➡|NET December 2019 Let G = (V, T, S, P) be any context-free grammar without any λ-productions or unit productions. Let K be the maximum number of symbols on the right of any production P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by:
Q20➡| NET December 2019 Consider Σ = {w, x} and T = {x, y, z}. Define homomorphism h by : h(x) = xzy h(w) = zxyy If L is the regular language denoted by r=(w+x*)(ww)*. then the regular language h(L) is given by
Q21➡|NET December 2019 Consider the following statements: S1: These exists no algorithm for deciding if any two Turning machine M1 and M2 accept the same language. S2: Let M1 and M2 be arbitrary Turing machines. The problem to determine L(M1)⊆ L(M2)is undecidable.
Q23➡|NET December 2019 Let A = (001, 0011, 11, 101} and B = (01, 111, 111, 010}. Similarly, let C = {00, 001, 1000} and D = {0, 11,011}. Which of the following pairs have a post-correspondence solution?
Q26➡| NET June 2019 Which of the following problems is/are decidable problem(s) (recursively enumerable) on a Turing machine M? (a) G is a CFG with L(G)=∅ (b) There exist two TMs M1 and M2 such that L(M) ⊆{L(M1)UL(M2)}= language of all TMs (c) M is a TM that accepts w using a most 2|w| cells of tape
Q27➡| NET June 2019 For a statement A language L ⊆ Σ* is recursive if there exists some Turing machine M Which of the following conditions is satisfied for any string w?
i ➥ If w ε L, then m accepts w and M will not halt
ii ➥ If w ∉ L, then M accepts w and M will halt by reaching at final state
iii ➥If w ∉ L, then M halts without reaching to acceptable state
iv ➥If w ε L, then M halts without reaching to an acceptable state
Q28➡| NET June 2019 Match List-I with List-II: Where L1 : Regular language L2 : Context-free language L3 : Recursive language L4 : Recursively enumerable language Choose the correct from those given below:
Q29➡| NET June 2019 How can the decision algorithm be constructed for deciding whether context-free language L is finite? (a) By constructing redundant CFG in CNF generating language L (b) By constructing non-redundant CFG G in CNF generating language L (c) By constructing non-redundant CFG in CNF generating language L-{∧} (∧ stands for null) Which of the following is correct?
Q30➡| NET June 2019 How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression is a*b(a+b).
Q31➡| NET June 2019 Consider the following grammar: S→ XY X→ YaY | a and y → bbX Which of the following statements is/are true about the above grammar? (a) Strings produced by the grammar can have consecutive three a’s (b) Every string produced by the grammar have alternate a and b (c) Every string produced by the grammar have at least two a’s (d) Every string produced by the grammar have b’s in multiple of 2.
Q32➡| NET December 2018 Consider the following two languages: L 1 = {X| for some y with | Y| = 2 |X| , XY∈ L and L is regular language} L 2 = { X | for some y such that |X| = |Y|, XY∈ L and L is regular language} Which one of the following is correct?
Q33➡| NET December 2018 Consider the following language: L 1 = { an+m bn am | n, m ≥ 0 } L 2 = { an+m bn+m an+m |n, m ≥ 0 } Which one of the following is correct?
i ➥ Only L 1 is Context Free Language
ii ➥ Both L 1 and L 2 are not Context Free Language
Q34➡| NET December 2018 Consider the following problems: (i) Whether a finite automaton halts on all inputs? (ii) Whether a given Context Free Language is regular? (iii) Whether a Turing Machine computes the product of two numbers? Which one of the following is correct?
Q35➡|NET December 2018 Consider the language L given by L = { 2nk | k > 0 , and n is non−negative integer number } The minimum number of states of finite automaton which accept the language L is
Q37➡| NET December 2018 Consider R to be any regular language and L1, L2 be any two context-free languages Which one of the following is correct ? A. (L1 ⋃ L2 ) − R is context free B. L’1 is context free C. L1 − R is context free D. L1 ⋂ L2 is context free
Q52➡| NET November 2017 Paper III Consider the following languages: L1 = {am bn │ m ≠ n} L2 = {am bn │ m = 2n+1} L3 = {am bn │ m ≠ 2n} Which one of the following statement is correct ?
Q53➡| NET January 2017 Paper II Which of the following strings would match the regular expression : p+ [3 – 5]∗ [xyz]? I. p443y II. p6y III. 3xyz IV. p35z V. p353535x VI. ppp5
Q54➡| NET January 2017 Paper III Which of the following are not regular? (A) Strings of even number of a’s. (B) Strings of a’s, whose length is a prime number. (C) Set of all palindromes made up of a’s and b’s. (D) Strings of a’s whose length is a perfect square.
Q56➡| NET January 2017 Paper III Given the following statements : (A) A class of languages that is closed under union and complementation has to be closed under intersection. (B) A class of languages that is closed under union and intersection has to be closed under complementation. Which of the following options is correct?
Q57➡| NET January 2017 Paper III Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that
Q58➡| NET January 2017 Paper III Given the following two languages: L1= {an bn | n ≥ 0, n ≠ 100} L2 = {w ∈ {a, b, c}*| na(w) = nb(w) = nc(w)} Which of the following options is correct ?
i ➥ Both L1 and L2 are not context free language
ii ➥ Both L1 and L2 are context free language.
iii ➥ L1 is context free language, L2 is not context free language.
iv ➥ L1 is not context free language, L2 is context free language.
Q59➡| NET January 2017 Paper III Given the following two statements : A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear. B. L = {an bn} ∪ {an b2n} is linear, but not deterministic context free language. Which of the following options is correct ?
Q62➡| NET June 2016 Paper II The number of strings of length 4 that are generated by the regular expression (0|∈)1+ 2* (3|∈), where | is an alternation character, {+, *} are quantification characters, and ∈ is the null string, is :
Q64➡| NET June 2016 Paper III Consider the following identities for regular expressions: (a) (r + s)* = (s + r)* (b) (r*)* = r* (c) (r* s*)* = (r + s)* Which of the above identities are true?
Q65➡|NET June 2016 Paper III Given the following two languages : L1 = {uwwRν | u, v, w ∈ {a, b}+} L2 = {uwwRν | u, ν, w ∈ {a, b}+, |u| > |ν|} Which of the following is correct ?
i ➥ L1 is regular language and L2 is not regular language.
ii ➥ L1 is not regular language and L2 is regular language.
Q66➡| NET June 2016 Paper III Given a Turing Machine M = ({q0 , q1 }, {0, 1}, {0, 1, B}, δ, B, {q1 }) Where δ is a transition function defined as δ(q0 , 0) = (q0 , 0, R) δ(q0 , B) = (q1 , B, R) The language L(M) accepted by Turing machine is given as :
Q67➡| NET June 2016 Paper III Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → ν, with |ν| = k > 1. The derivation tree for any string W ∈ L (G) has a height such that
Q70➡| NET August 2016 Paper III Consider the following two languages : L1 = {0i1j| gcd (i, j) = 1} L2 is any subset of 0*. Which of the following is correct ?
Q71➡| NET August 2016 Paper III Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has____equivalence classes.
Q73➡| NET August 2016 Paper III Given a Turing Machine M = ({q0, q1,q2, q3}, {a, b}, {a, b, B}, δ, B, {q3}) Where δ is a transition function defined as δ( q0 , a) = ( q1 , a, R) δ( q1 , b) = ( q2 , b, R) δ( q2 , a) = ( q2 , a, R) δ( q3 , b) = ( q3, b, R) The language L(M) accepted by the Turing Machine is given as:
Q76➡| NET December 2015 Paper III The language of all non-null strings of a’s can be defined by a context free grammar as follows: S → aS|Sa|a The word a3 can be generated by _________different trees.
Q77➡| NET December 2015 Paper III The context free grammar given by S → XYX X → aX|bX|λ Y → bbb generates the language which is defined by regular expression:
Q77➡| NET December 2015 Paper III There are exactly __ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.
Q79➡| NET December 2015 Paper III Given the following two languages: L1 = {an b an |n > 0} L2 = {an b an bn + 1|n > 0} Which of the following is correct ?
i ➥ L1 is context free language and L2 is not context free language
ii ➥ L1 is not context free language and L2 is context free language
iii ➥ Both L1 and L2 are context free languages
iv ➥ Both L1 and L2 are not context free languages
Q80➡| NET December 2015 Paper III Consider a language A defined over the alphabet Σ={0, 1} as A={0⌊n/2⌋1n :n>=0}. The expression ⌊n/2⌋ means the floor of n/2, or what you get by rounding n/2 down to the nearest integer. Which of the following is not an example of a string in A?
Q82➡| NET JUNE 2015 Paper III The regular expression corresponding to the language L where L = { x ε {0, 1}*|x ends with 1 and does not contain substring 00 } is:
Q85➡| NET JUNE 2015 Paper III Given the following two statements: S1 : If L1 and L2 are recursively enumerable languages over ∑ , then L1 ∪ L2 and L2 ∩ L2 are also recursively enumerable. S2 : The set of recursively enumerable languages is countable. Which of the following is correct ?
Q86➡| NET JUNE 2015 Paper III Given the following grammars: G1 : S → AB|aaB A → aA | ∈ B → bB | ∈ G2: S → A|B A → aAb | ab B → abB | ∈ Which of the following is correct?
i ➥ G1 is ambiguous and G2 is unambiguous grammars
ii ➥ G1 is unambiguous and G2 is ambiguous grammars
Q87➡| NET Dec 2014 Paper III Given two languages : L1 = {(ab)n ak | n > k, k ≥ 0} L2 = {an bm | n ≠ m} Using pumping lemma for regular language, it can be shown that
Q89➡| NET Dec 2014 Paper III Given the recursively enumerable language (LRE), the context sensitive language (LCS), the recursive language (LREC), the context free language (LCF) and deterministic context free language (LDCF). The relationship between these families is given by
Q91➡| NET Dec 2014 Paper III According to pumping lemma for context free languages : Let L be an infinite context free language, then there exists some positive integer m such that any w ∈ L with | w | ≥ m can be decomposed as w = u v x y z
i ➥ with | vxy | ≤ m such that uvi xyi z ∈ L for all i = 0, 1, 2
ii ➥ with | vxy | ≤ m, and | vy | ≥ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
iii ➥ with | vxy | ≥ m, and | vy | ≤ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
iv ➥ with | vxy | ≥ m, and | vy | ≥ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
Q93➡| NET JUNE 2014 Paper II The regular grammar for the language L = {w|na(w) and nb(w) are both even, w ∈ {a, b}*} is given by : (Assume, p, q, r and s are states)
i ➥ p → aq | br | λ, q → bs | ap r → as | bp, s → ar | bq, p and s are initial and final states.
ii ➥ p → aq | br, q → bs | ap r → as | bp, s → ar | bq, p and s are initial and final states.
iii ➥ p → aq | br | λ, q → bs | ap r → as | bp, s → ar | bq p is both initial and final states.
iv ➥ p → aq | br, q → bs | ap r → as | bp, s → ar | bq p is both initial and final states
Q94➡| NET JUNE 2014 Paper III Let L be any language. Define even (W) as the strings obtained by extracting from W the letters in the even-numbered positions and even(L) = {even (W) | W ∈ L}. We define another language Chop (L) by removing the two leftmost symbols of every string in L given by Chop(L) = {W | ν W ∈ L, with | ν | = 2}. If L is regular language then
i ➥ even(L) is regular and Chop(L) is not regular
ii ➥ Both even(L) and Chop(L) are regular
iii ➥ even(L) is not regular and Chop(L) is regular
=1, m>=1 }”>
