Q. Which of the following problems occur?
1) Does a given program ever produce an output?

2) If L is a CFL, then is L’ is also context-free?

3)L’ is regular only if L is regular?

4) If L is a recursive language, then, L’ is also recursive?

View solution

Q. Definition of a language L with alphabet {a} is given as following. L= { ank | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?

View solution

Q. S –> aSa| bSb| a| b ;the language generated by the above grammar is the set of

View solution

Q. 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)*?

View solution

Q. Match the following
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

View solution

Q. Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:
L1 = {ambmcanbn | m, n >= 0 }

L2 = {aibjck | i, j, k >= 0 }

Then L is

View solution

Q. Does epsilon ring any change in the automata

View solution

Q. NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA.

View solution

Q. E(q) is known ε-closure of q.

View solution

Q. ε-transitions does not add any extra capacity of recognizing formal

View solution

Q. A nondeterministic finite automaton with ε-moves is an extension of nondeterministic finite automaton

View solution

Q. Is an ordinary NFA and a NFA-ε are equivalent

View solution

Q. Which grammar is not regular

View solution

Q. If is a language, and is a symbol, then, the quotient of and, is the set of strings such that is in: is in. Suppose is regular, which of the following statements is true?

View solution

Q. Here is a context-free grammar G: S → AB A → 0A1 | 2 B → 1B | 3A which of the following strings are in L (G)?

View solution

Q. The grammar G: S → SS | a | b is ambiguous. Check all and only the strings that have exactly two leftmost derivations in G

View solution

Q. For the following grammar: S → A | B | 2 A → C0 | D B → C1 | E C → D | E | 3 D → E0 | S E → D1 | S Identify all the unit pairs

View solution

Q. The classes of languages P and NP are closed under certain operations, and not closed under others. Decide whether P and NP are closed under each of the following operations.
1. Union

2. Intersection

3. Intersection with a regular language

4. Kleene closure (star)

5. Homomorphism

View solution

Q. Ndfa and dfa accept same languages

View solution

Q. If the NFA N has n states, then the corresponding DFA D has 2n states

View solution