Theory of Computation
Welcome to NTA NET ASPIRANT ACADEMY
NTA NET ASPIRANT ACADEMY is a training academy for College Lectures, Assistant Professor, Research Scholar and PG Students to make qualified for Assistant Professor & JRF in UGC NET / TNSET
NTA NET ASPIRANT ACADEMY is a training academy for College Lectures, Assistant Professor, Research Scholar and PG Students to make qualified for Assistant Professor & JRF in UGC NET / TNSET
Start
Congratulations - you have completed Theory of Computation.
You scored %%SCORE%% out of %%TOTAL%%.
Your performance has been rated as %%RATING%%
Your answers are highlighted below.
Question 1 |
Which of the following statements is true? NTA NET JUNE 2020
A | The union of two context free language is context free. |
B | The intersection of two context free languages is context free. |
C | The complement of a context free language is context free. |
D | If a language is context free, it can always be accepted by a deterministic pushdown automation. |
Question 2 |
Consider the following regular expressions: NTA NET JUNE 2020
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:
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:
A | L(r) ⊆ L(s) ⊆ L(t) |
B | L(r) ⊇ L(s) ⊇ L(t) |
C | L(r) ⊇ L(t) ⊇ L(s) |
D | L(s) ⊇ L(t) ⊇ L(r) |
Question 3 |
Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language. Consider the following problems: NTA NET JUNE 2020
A. Is L(G1) = L(G2)?
B. Is L(G1) ≤ L(G2)?
C. Is L(G1) = R?
Which of the problems are undecidable?
Choose the correct answer from the options given below:
A. Is L(G1) = L(G2)?
B. Is L(G1) ≤ L(G2)?
C. Is L(G1) = R?
Which of the problems are undecidable?
Choose the correct answer from the options given below:
A | (A) only |
B | (B) only |
C | (A) and (B) only |
D | (A), (B) and (C) only |
Question 4 |
Given below are two statements: NTA NET JUNE 2020
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
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
A | Both Statement I and Statement II are true. |
B | Both Statement I and Statement II are false. |
C | Statement I is true but Statement II is false. |
D | Statement I is false but Statement II is true. |
Question 5 |
Which of the following are applications of symbol table? NTA NET JUNE 2020
A. Storage allocation
B. Checking type compatability
C. Suppressing duplicate error messages.
Choose the correct answer from the options given below:
A. Storage allocation
B. Checking type compatability
C. Suppressing duplicate error messages.
Choose the correct answer from the options given below:
A | (A) and (B) only |
B | (A) and (C) only |
C | (B) and (C) only |
D | (A),(B) and (C) only |
Question 6 |
Match List I with List II: NTA NET JUNE 2020
LR: Regular language
LCF: Context free language
LREC: Recursive language
LRE: Recursively enumerable language.
Choose the correct answer from the options given below:
LR: Regular language
LCF: Context free language
LREC: Recursive language
LRE: Recursively enumerable language.
| List - I | List - II |
|---|---|
| A. Recursively Enumerable Language | (i) ḸREC ⋃ ḸRE |
| B. Recursive Language | (ii) ḸCF ⋃ ḸREC |
| C. Context free Language | (iii) L*R ⋂ LCF |
A | A - ii, B - iii, C - i |
B | A - iii, B - i, C - ii |
C | A - i, B - ii, C - iii |
D | A - ii, B - i, C - iii |
Question 7 |
Which of the following grammars is / are ambiguous? NTA NET JUNE 2020
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:
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:
A | (A) and (C) only |
B | (B) only |
C | (B) and (C) only |
D | (A) and (B) only |
Question 8 |
Consider L = L1 ⋂ L2 NTA NET JUNE 2020
Where L1 = {0m1m20n1n | m,n ≥ 0}
L2 = {0m1n2k | m,n,k ≥ 0}
Then, the language L is
Where L1 = {0m1m20n1n | m,n ≥ 0}
L2 = {0m1n2k | m,n,k ≥ 0}
Then, the language L is
A | Recursively enumerable but not context free |
B | Regular |
C | Context free but not regular |
D | Not recursive |
Question 9 |
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?
- L1 ⊂ L2
- L2 ⊂ L1
- L1 = L2
- L1 ⋂ L2 = ϕ
A | Option 1 |
B | Option 2 |
C | Option 3 |
D | Option 4 |
Question 10 |
Consider the following grammar: NTA NET December 2019
S → 0A | 0BB
A → 00A | λ
B → 1B | 11C
C → B
Which language does this grammar generate?
S → 0A | 0BB
A → 00A | λ
B → 1B | 11C
C → B
Which language does this grammar generate?
A | L((00)*0+(11)*1) |
B | L(0(11)*+1(00)*) |
C | L((00)*0) |
D | L(0(11)*1) |
Question 11 |
Consider the following grammars: NTA NET December 2019
G1: S → aSb | bSa | aa
G2: S → aSb | bSa | SS | λ
G3: S → aSb | bSa | SS | a
G4: S → aSb | bSa | SS | SSS | λ
Which of the following is correct with respect to the above grammars?
G2: S → aSb | bSa | SS | λ
G3: S → aSb | bSa | SS | a
G4: S → aSb | bSa | SS | SSS | λ
Which of the following is correct with respect to the above grammars?
A | G1 and G3 are equivalent |
B | G2 and G3 are equivalent |
C | G2 and G4 are equivalent |
D | G3 and G4 are equivalent |
Question 12 |
Consider the following statements with respect to the language L={anbn | n≥0} NTA NET December 2019
S1: L2 is context free language.
S2: Lk is context free language for any given k≥1.
S3: L̅ and L* are context free language.
Which of the following is correct?
S1: L2 is context free language.
S2: Lk is context free language for any given k≥1.
S3: L̅ and L* are context free language.
Which of the following is correct?
A | Only S1 and S2 |
B | Only S1 and S3 |
C | Only S2 and S3 |
D | S1, S2 and S3 |
Question 13 |
Consider the following language families: NTA NET December 2019
L1 ≡ The Context - free languages.
L2 ≡ The Context - sensitive languages.
L3 ≡ The Recursively enumerable languages.
L4 ≡ The Recursive languages.
Which one of the following options is correct?
L1 ≡ The Context - free languages.
L2 ≡ The Context - sensitive languages.
L3 ≡ The Recursively enumerable languages.
L4 ≡ The Recursive languages.
Which one of the following options is correct?
A | L1 ⊆ L2 ⊆ L3 ⊆ L4 |
B | L2 ⊆ L1 ⊆ L3 ⊆ L4 |
C | L1 ⊆ L2 ⊆ L4 ⊆ L3 |
D | L2 ⊆ L1 ⊆ L4 ⊆ L3 |
Question 14 |
Consider the language L={anbn-3 | n>2} on ∑={a,b}. Which one of the following grammars generates the language L? NTA NET December 2019
A | S → aA | a, A → aAb | b |
B | S → aaA | λ, A → aAb | λ |
C | S → aaaA | a, A → aAb | λ |
D | S → aaaA, A → aAb | λ |
Question 15 |
Consider the following statements: NTA NET December 2019
S1: There exists no algorithm for deciding if any two Turing machines 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.
Which of the statements is / are correct?
S1: There exists no algorithm for deciding if any two Turing machines 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.
Which of the statements is / are correct?
A | Only S1 |
B | Only S2 |
C | Both S1 and S2 |
D | Neither S1 nor S2 |
Question 16 |
Consider the following languages: NTA NET December 2019
L1 = {anbncm} υ {anbmcm} n,m≥0
L2 = {wwR | w ϵ{a,b}*} Where R represents reversible operation.
Which one of the following is / are inherently ambiguous language(s)?
L1 = {anbncm} υ {anbmcm} n,m≥0
L2 = {wwR | w ϵ{a,b}*} Where R represents reversible operation.
Which one of the following is / are inherently ambiguous language(s)?
A | Only L1 |
B | Only L2 |
C | Both L1 and L2 |
D | Neither L1 nor L2 |
Question 17 |
Two finite state machines are said to be equivalent if they: CBSE NET JULY 2018
A | Have the same number of edges |
B | Have the same number of states |
C | Recognize the same set of tokens |
D | Have the same number of states and edges |
Question 18 |
A pushdown automata behaves like a Turing machine when the number of auxiliary memory is: CBSE NET JULY 2018
A | 0 |
B | 1 |
C | 1 or more |
D | 2 or more |
Question 19 |
Pushdown automata can recognize language generated by ________. CBSE NET JULY 2018
A | Only context free grammar |
B | Only regular grammar |
C | Context free grammar or regular grammar |
D | Only context sensitive grammar |
Question 20 |
To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of production to be used is: CBSE NET JULY 2018
A | 2n-1 |
B | 2n |
C | n+1 |
D | n^2 |
Question 21 |
Consider the following two Grammars: CBSE NET JULY 2018
G1: S → SbS | a
G2: S → aB | ab, A → GAB | a, B → ABb | b
Which of the following option is correct?
G1: S → SbS | a
G2: S → aB | ab, A → GAB | a, B → ABb | b
Which of the following option is correct?
A | Only G1 is ambiguous |
B | Only G2 is ambiguous |
C | Both G1 and G2 are ambiguous |
D | Both G1 and G2 are not amniguous |
Question 22 |
Context sensitive language can be recognized by a: CBSE NET JULY 2018
A | Finite state machine |
B | Deterministic finite automata |
C | Non Deterministic finite automata |
D | Linear bounded automata |
Question 23 |
The set A = { 0n1n2n | n=1,2,3,.....} is an example of a grammar that is: CBSE NET JULY 2018
A | Context sensitive |
B | Context free |
C | Regular |
D | None of the above |
Question 24 |
A bottom up parser generates: CBSE NET JULY 2018
A | Left most derivation in reverse |
B | Right most derivation in reverse |
C | Left most derivation |
D | Right most derivation |
Question 25 |
Consider the following statements(): CBSE NET JULY 2018
S1: There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language. S2: The problem of determining whether a Turing machine halts on any input is undecidable.
Which of the following options is correct?
S1: There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language. S2: The problem of determining whether a Turing machine halts on any input is undecidable.
Which of the following options is correct?
A | Both S1 and S2 are correct |
B | Both S1 and S2 are not correct |
C | Only S1 is correct |
D | Only S2 is correct |
Once you are finished, click the button below. Any items you have not completed will be marked incorrect.
Get Results
There are 25 questions to complete.
You have completed
questions
question
Your score is
Correct
Wrong
Partial-Credit
You have not finished your quiz. If you leave this page, your progress will be lost.
Correct Answer
You Selected
Not Attempted
Final Score on Quiz
Attempted Questions Correct
Attempted Questions Wrong
Questions Not Attempted
Total Questions on Quiz
Question Details
Results
Date
Score
Hint
Time allowed
minutes
seconds
Time used
Answer Choice(s) Selected
Question Text
All done
Need more practice!
Keep trying!
Not bad!
Good work!
Perfect!