Theory of Computation
Q81.
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 \varepsilon-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 \rightarrow w or x \rightarrow 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 treesQ82.
Consider the following language: L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \} Which one of the following deterministic finite automata accepts L?Q83.
Minimum number of states required in DFA accepting binary strings not ending in "101" isQ84.
Consider the following deterministic finite automaton (DFA)The number of strings of length 8 accepted by the above automaton is _________Q85.
Given a language L, define L^{i} as follows: L^{0}=\{\varepsilon \} L^{i}=L^{i-1} \cdot L for all i \gt 0 The order of a language L is defined as the smallest k such that L^{k}=L^{k+1}. Consider the language L1 (over alphabet 0) accepted by the following automaton. The order of L1 is ______Q86.
The minimum possible number of states of a deterministic automaton that accepts the regular language L=\{w_{1}aw_{2}|w_{1},w_{2}\in \{a,b\}^{*},|w_{1}|=2,|w_{2}|\geq 3\} is ____Q87.
Let \Sigma be the set of all bijections from {1,...,5} to {1,...,5}, where id denotes the identity function, i.e. id(j)=j,\forall j. Let \circ denote composition on functions. For a string x = x_1x_2 ... x_n \in \Sigma ^n, n \geq 0, let \pi(x) = x_1\circ x_2\circ ... \circ x_n. Consider the language L = \{x \in \Sigma ^* | \pi(x) = id\}. The minimum number of states in any DFA accepting L is _________ .Q88.
Consider the language L over the alphabet {0, 1}, given below:L = \{w \in \{0, 1\}^* | w \text{ does not contain three or more consecutive 1's} \}. The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is _____.Q89.
Let \delta denote that transition function and \hat{\delta} denote the extended transition function of the \epsilon- NFA whose transition table is given below: Then \hat{\delta}(q_{2},aba) is ____