Test 2 - Theory of Computation | Computer Science(CS)
| Description: GATE Previous year Topic Wise Questions and Answers | Theory of Computation | |
| Number of Questions: 21 | |
| Created by: Aliensbrain Bot | |
| Tags: Theory of Computation GATE CS |
Consider the following Finite State Automaton:
The language accepted by this automaton is given by the regular expression
The language {0i 21i | i $\ge$0} over the alphabet {0, 1, 2} is:
A minimum state deterministic finite automaton accepting the language L = {w | w $\in${0, 1}*, number of 0s and 1s in w are divisible by 3 and 5, respectively} has
Which of the following statements is false?
Which of the following is true for the language $\left\{ a^p \text{ | p is a prime} \right\} $?
Consider the following Finite State Automaton:
The minimum state automaton equivalent to the above FSA has the following number of states
So only 2 statesWhich of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-free
If L and $\bar L$ are recursively enumerable then L is
S $\rightarrow$ aSa | bSb | a | b; The language generated by the above grammar over the alphabet {a, b} is the set of
Which one of the following languages over the alphabet {0, 1} is described by the regular expression: (0 + 1)0(0 + 1)*0(0 + 1)?
Which of the following are regular sets?
I. $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ II. $\left\{a^nb^m \mid n =2m \right\}$ III. $\left\{a^nb^m \mid n \neq m \right\}$ IV. $ \left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\} $
Which of the following statements are true?
I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa II. All $\epsilon$ productions can be removed from any context-free grammar by suitable transformations III. The language generated by a context-free grammar all of whose productions are of the form X --> w or X --> wY (where, w is a string of terminals and Y is a non-terminal), is always regular IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
Which of the following languages is regular?
Which one of the following is FALSE?
The above DFA accepts the set of all strings over {0, 1} that
Match the following NFAs with the regular expressions they correspond to
- $ \epsilon + 0 \left(01^*1+00\right)^*01^*$
- $ \epsilon + 0 \left(10^*1+00\right)^*0$
- $ \epsilon + 0 \left(10^*1+10\right)^*1$
- $ \epsilon + 0 \left(10^*1+10\right)^*10^*$
Match all items in Group 1 with correct options from those given in Group 2.
Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization
Let L = L1 $\cap$ L2, where L1 and L2 are languages as defined below: L1 = $(a^m b^m\ ca^n b^m | m,n \ge 0)$ L2 = $(a^i b^j\ c^k | i,j \ge 0)$ Then L is
Match the following:
| E. | Checking that identifiers are declared before their use | P. | $L : = : \left\{a^nb^mc^nd^m \mid n: \geq1, m \geq 1\right\}$ | |
| F. | Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function | Q. | $X: \rightarrow XbX \mid XcX \mid dXf \mid g$ | |
| G. | Arithmetic expressions with matched pairs of parentheses | R. | $L: = \left\{wcw\mid w : \in \left(a\mid b\right)^* \right\}$ | |
| H. | Palindromes | S. | $X : \rightarrow : bXb \mid :cXc : \mid \epsilon $ |
Given the following state table of an FSM with two states A and B, one input and one output:
| Present State A | Present State B | Input | Next State A | Next State B | Output |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 |
If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?
Given below are two finite state automata (→ indicates the start state and F indicates a final state)
Y:
| a | b | |
|---|---|---|
| $\rightarrow$ 1 | 1 | 2 |
| 2(F) | 2 | 1 |
Z:
| a | b | |
|---|---|---|
| $\rightarrow$ 1 | 2 | 2 |
| 2(F) | 1 | 1 |
Which of the following represents the product automaton Z × Y?
