Time Left - 10:00 mins

ISRO 2018: TOC Booster Quiz- 3

Attempt now to get your rank among 977 students!

Question 1

Consider the following Deterministic Finite Automaton $M$ .

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 2

S –> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a, b} is the set of

Question 3

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?

Question 4

An FSM (Finite State Machine) can be considered to be a TM (Turing Machine) of finite tape length

Question 5

Given the following statements
S1: Every context-sensitive language L is recursive
S2: There exists a recursive language that is not context-sensitive
Which statements are true?

Question 6

The problems 3-SAT and 2-SAT are

Question 7

If L and P are two recursively enumerable languages, then they are not closed under

Question 8

Palindromes can’t be recognized by any Finite State Automata because :

977 attempts
4 upvotes
9 comments

Tags :

GATE & PSU CS Theory of Computation

Mar 25GATE & PSU CS