TOC MCQ

The context-free languages are closed for:

(i) Intersection                          (ii) Union
(iii) Complementation             (iv) Kleene Star

• 1. (i) and (iii)

• 
  (ii) and (iv)

• 1. 
     (ii) and (iii)

• 1. 
     (ii) and (iv)

Match the List I with List II

• 
• 
• 
• 

Which of the following statement is True?

• 1. Every DFA is NFA, but NFA is not DFA

• 1. Every DFA is NFA, also every NFA is DFA

• 1. NFA is faster to process and its representation uses less memory than DFA

• DFA is slower to process and its representation uses less memory than NFA

DFA Transition function can be defined as ____.

• 1. W: Q x ∑→Q

• 1. δ: Q x ∑→W

• δ: Q x ∑→Q

• 1. δ: Q x ∑→F

What will be the regular expression for the language accepting all the strings which are starting with 1 and ending with 0, over ∑ = {0, 1}?

• 1. R = 1 (0+1)* 1

• 1 (0+1)+1

• 1 (0+1)+ 0

• R = 1 (0+1)* 0

Context-free grammar can be recognized by ____.

• 1. Finite Automaton

• 1. Pushdown Automaton

• 1. Turing Machine

• 1. Popdown Automaton

Which of the following is a regular language?

• {aⁱbⁱ|i>=0}

• {aⁱbⁱ|i>=1}

• {aⁱbⁱ|0<i<5}

The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?

• Sensitive Grammar

• Starting Variable

• Accepting State

• Transitions

Which of the following is the correct description of language recognized by the DFA?

• Sets of binary strings with atleast two 1's

• Sets of binary strings which contains 110 as substring

• Sets of binary strings which ends with 11

• Sets of binary strings which has even number of 11's

Given Grammar G:
S->aA
A->a| A
B->B

The number of productions to be removed immediately as Unit productions:

• 2

• 1

• 3

• 0