Bihar STET 2024
FA: Most restricted type of Computer Science Paper 2 ( 0226)
machine that accepts only
regular lang. Theory of Computa on Mock Paper
[Link]
2. NFA
1. For specified input, there can be how many paths from current state to
the next state in DFA ? Symbol: Fundamental/basic unit of language
a. Zero Alphabet:Finite set of symbols
Strings:Collection of alphabets
b. One Language:Collection of all possible strings
c. Two
Write a regular exp for a language that accepts a
d. Many string that end with 'a'.
Ex-> aba, a, abba, ba
2. A _______ machine is a finite state machine in which the output does
not change when we change the input. (a+b)*a
a. Mealy Automata is a machine
b. Moore used to check whether the Kleen's star/closure
string is part of lang or not.
c. Both
Moore: Output only depends on
d. None of these present state.
V, T, P, S
It is sync with clock
CFG: Context For n length symbol, it will return
3. The Deriva on tree is also known as ________ output of len n+1;
Free Language
a. Comprehend Tree More no. of states are required
PDA is used. b. Decipher Tree Mealy:
c. Deviated Tree Output depends on current
state and current input symbol
d. Parse Tree Async with clock
For n len input then it will return
output of len n.
4. Which of the following statement is true? Less no. states are required.
a. Every Type 2 language is Type 1 and Type 3.
b. Every Type 2 language is Type 3 and Type 0.
c. Every Type 2 language is Type 1 and Type 0.
d. None of these
5. According to Chomsky’s Hierarchy which of the following represents
unrestricted grammar?
a. Type 3
b. Type 2
c. Type 1
d. Type 0
6. Recursively Enumerable Language is not closed under –
a. Complementa on Union: +
b. Union Concatenation: .
Complementation:
c. Intersec on Intersection: common
d. None of these Difference: L1 - L2
Kleen Closure: *
Positive Closure: +
7. What is the reason behind a Turing Machine is more powerful than
Drawbacks of FA:
Finite State Machine ? Limited Memory
a. Turing machine head movement is con nued in one direc on Limited power
b. Turing machine head movement is in both direc ons Strings without
comparison
c. Turing machine has capability to remember arbitrary long sequence
of input string PDA:
Stack Memory
d. All of these String with comparion
TM: FA+2stack+Infinite Input Tape
8. A PDA behaves like Turing machine when it has ______ number of
auxiliary memory.
a. Zero
b. One
c. Exactly Two
d. Two or more
9. A universal turing machine is a –
a. Reprogrammable Turing machine
b. Two tape turing machine
c. Single Tape Turing machine
d. None of these
10. The behaviour of NFA can be simulated using DFA-
a. Always
b. Never Every NFA can be translated in its equivalent DFA.
c. Some mes
d. None of the men oned
3 problems: Decidable, Semi-decidable, Undecidable
Accept, Reject, Never Halt
11. Hal ng state are of two type. They are –
a. Reject and Allow
b. Accept and Stop
c. Accept and Reject
d. Start and Reject
12.A PDA can be defined as : (Q,∑,G,q0,z0,A,d). What does symbol z0
represents?
a. An element of G Q- set of all states
b. Ini al stack symbol E: Set of Alphabets
G: Stack Alphabet
c. Top stack alphabet Q0 = Initial State
d. All of these z0 -> stacksymbol
A -> Accepting state
D -> Transition Func
13. The produc on of the form A-> B, where A and B are non-terminals is
called –
a. Null Produc on
b. Unit Produc on
c. Chomsky Normal Form
d. Greibach Normal Form
A-> BC
A-> aX A-> a
14. (0 + e)(1 + e) represents –
a. {0, 1, 01, e}
b. {0, 1, e}
c. {0, 1, 01, 10, 11, 00, 10, e}
d. {0,1}
15. The Context Free Language is closed for-
a. Intersec on
b. Union
c. Complementa on
d. None of these
16. Grammars that can be translated to DFA is –
a. Le Linear Grammar
b. Right Linear Grammar
c. Generic Grammar
d. All of these
[Link] logic of pumping lemma is a good example of –
a. Pigeon hole principle
b. Recursion
c. Divide and Conquer Algorithm
d. Itera on
18. Which sentence can be generated by S -> d/bA , A -> d/ccA –
a. bccddd
b. aabccd
c. ababccd
d. abbbd
19. Regular expression for the language L= { w ∈ {0, 1}* | w has no pair of
consecutive zeros} is –
a. (1 + 010)*
b. (01 + 10)*
c. (1 + 010)*(0 + 1)
d. (1 + 01)*(0 + 1)
20. Which of the following statement is false?
a. Every context sensi ve language is recursive.
b. The set of all languages that are not recursively enumerable is
countable.
c. The family of recursively enumerable languages is closed under
union.
d. The families of recursively enumerable and recursive languages are
closed under reversal.