Time Left - 10:00 mins
Mission ISRO 2017 Day-14: Theory of Computation Quiz-1
Attempt now to get your rank among 378 students!
Question 1
What is the number of steps required to derive the string ((() ()) ()) for the following grammar.
S
SS
S
(S)
S
S
SS S
(S) S
Question 2
What is the best suitable type that can be assigned to this following grammar:
S→Aa, A→Ba, B→abc
Question 3
Which of the following sentences can be generated by
S -> aS l bA
A -> d l cA
S -> aS l bA
A -> d l cA
Question 4
Consider the following grammar.
S
AB
A
a
A
BaB
B
bbA
Which of the following statements is false?
S
AB A
a A
BaB B
bbA Which of the following statements is false?
Question 5
The number of states required by a Finite State Machine, to simulate the behavior of a computer with a memory capable of storing 'm' words, with each word being 'n' bits long is
Question 6
The following Finite Automation recognizes which language?
Question 7
S –> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a, b} is the set of
Question 8
Consider the grammar
S→ABCc | bc
BA→AB
Bb→bb
Ab→ab
Aa→aa
C→b
Which of the following sentences can be derived by this grammar?
S→ABCc | bc
BA→AB
Bb→bb
Ab→ab
Aa→aa
C→b
Which of the following sentences can be derived by this grammar?
Question 9
Consider the following Deterministic Finite Automaton MM.
Let S denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in S that are accepted by M is
Question 10
What are the final states of the DFA generated from the following NFA?
- 378 attempts
- 0 upvotes
- 8 comments
Apr 2GATE & PSU CS
