Theory Of Computation Unit 3 Set 1

Q1 | If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ?

Q2 | Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively

Q3 | If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

Q4 | The logic of pumping lemma is a good example of

Q5 | For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by

Q6 | Pumping lemma is generally used for proving that

Q7 | What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc

Q8 | Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding productionA —>aB {print “(1)” A —> c {print “1”),B —>Ab {print *2”}.When parser is aaacbbb, then string printed

Q9 | FSM can recognize

Q10 | Basic limitation of FSM is that it

Q11 | Which of the following are decidable?1) Whether the intersection of two regular language is infinite.2) Whether a given context free language is regular.3) Whether two push down automata accept the same language.4) Whether a given grammar is context free.

Q12 | If L and L¯ are recursively enumerable, then L is

Q13 | Which of the following problems is undecidable?

Q14 | Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)

Q15 | Which of the following statements is/are FALSE?(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.(2) Turing recognizable languages are closed under union and complementation.(3) Turing decidable languages are closed under intersection and complementation(4) Turing recognizable languages are closed under union and intersection.

Q16 | Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is

Q17 | Which statement is true?

Q18 | Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Q19 | Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?

Q20 | Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is:

Q21 | Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.

Q22 | The production Grammar is {S->aSbb,S->abb} is

Q23 | Regular expression (x/y)(x/y) denotes the set

Q24 | Which one of the following is true regarding FOTRAN?

Q25 | TM is more powerful than FSM because