Test my Merit My Results Create Exam

Higher Study | Theory of Computation

Context Free Languages and Pushdown Automata Regular Languages and Finite Automata Recursively Enumerable Sets
Which of the following statement(s) is/are FALSE? (i) There exists a recursively enumerable language whose complement is not recursively enumerable. (ii) If a language L is recursive, then its complement is NOT recursive.
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
Which of the following languages over the alphabet ∑ = {0, 1} is regular? I. 0n1m II. 0n1m where m = n + 1 III. 0m1n where m ≡ n (mod 3).
Consider L = L1 ∩ L2 Where L1 = {0m1m20n1n |m, n >= 0} L2 = {0m1n2k | m, n, k ≥ 0} Then, the language L is
Which of the following grammars is (are) ambiguous? (A) s → ss | asb | bsa | (B) s → asbs | bsas | λ (C) s → aAB A → bBb B →  A | λ where λ denotes empty string Choose the correct answer from the options given below:
Which of the following statements is/are TRUE? (a) The grammar S → SS | a is ambiguous. (Where S is the start symbol) (b) The grammar S → 0S1 | 01S |e is ambiguous. (The special symbol e represents the empty string) (Where S is the start symbol) (c) The grammar (Where S is the start symbol) S → T / U T → x S y | xy | ϵ U → yT generates a language consisting of the string yxxyy.
Identify the language generated by the following grammar, where S is the start variable. S → XY X → aX | a Y → aYb | ϵ
If G is a grammar with productions S → SaS | aSb | bSa | SS | ∈ Where S is the start variable. Then which one of the following strings in not generated by G?
Consider the following languages: I. \(?^? ?^??^??^?| ? + ? = ? + ?, where \text{ ?}, ?, ?, ? ≥ 0\) II. \({?^??^??^??^?| ? = ? \text{ and } ? = ?, where \text{ ?}, ?, ?, ? ≥ 0}\) III. \(?^??^??^??^?| ? = ? = ? \text{ and } ? ≠ ?, where \text{ ?}, ?, ?, ? ≥ 0\) IV. \(?^??^??^??^?| ?? = ? + ?, where \text{ ?}, ?, ?, ? ≥ 0\) Which of the languages above are context-free?
Let L be the language represented by the regular expression Σ∗0011Σ∗ where Σ={0, 1}. What is the minimum number of states in a DFA that recognizes L̅ (complement of L)?
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
What is the complement of the language accepted by the NFA shown below? Assume ∑ = {a} and ϵ is the empty string
How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | ∈ (0,1)*, number of 0's is divisible by 2, and number of 1's is divisible by 5, respectively}?
Consider the FA shown in fig below which language is accepted by the FA:
What is the minimum number of states required by a Turing Machine to accept strings which consist of even number of 1's?
Ads