Let A = {0 1}. The number of possible strings of length n that can be formed by the elements of the set A is ___.

• A) n!
• B) n^2
• C) n^m
• D) 2^n

Choose the correct statement.

• A) A Mealy machine generates no language as such
• B) A Moore machine generates no language as such
• C) A Mealy machine has no terminal state
• D) All of these

TM is more powerful than FSM because ___.

• A) The tape movement is confined to one direction
• B) It has no finite state control
• C) It has the capability to remember arbitrary long sequences of input symbols
• D) None of these

Like TG a PDA can also be non-deterministic.

• A) True
• B) False
• C) Only partially
• D) None of given

Which of the following is NOT a regular language?

• A) String of 0's whose length is a perfect square
• B) Set of all palindromes made up of 0's and 1's
• C) String of 0's whose length is a prime number
• D) All of the given options

Left hand side of a production in CFG consists of:

• A) One terminal
• B) More than one terminal
• C) One non-terminal
• D) Terminals and non-terminals

PDA is only used to represent a regular language.

• A) True
• B) False
• C) Only CFL
• D) None of given

We can find a CFG corresponding to a DFA.

• A) True
• B) False
• C) Only NFA
• D) None of given

A CFG is said to be ambiguous if there exists at least one word of its language that can be generated by different production trees.

• A) True
• B) False
• C) Only sometimes
• D) None of given

Syntax tree or Generation tree or Derivation tree are same tree.

• A) True
• B) False
• C) Only partially
• D) None of given

The production of the form non-terminal to one non-terminal is called unit production.

• A) True
• B) False
• C) Only sometimes
• D) None of given

DFA and PDA are equal in power.

• A) True
• B) False
• C) Only for regular
• D) None of given

Semi-word is a string having some terminals and one non-terminal at the right of string.

• A) True
• B) False
• C) Only sometimes
• D) None of given

Two FAs are equivalent if they have same no. of states.

• A) True
• B) False
• C) Only sometimes
• D) None of given

Regular languages are closed under Union Concatenation and Kleene star.

• A) True
• B) False
• C) Only Union
• D) None of given

PDA is stronger than FA.

• A) True
• B) False
• C) Equal
• D) None of given

Set of all palindromes over {a b} is regular.

• A) True
• B) False
• C) Only sometimes
• D) None of given

a^n b^n generates the ___ language.

• A) regular
• B) non regular
• C) EQUAL and non regular
• D) EQUAL and regular

The grammatical rules which involves meaning of words are called:

• A) Semantic
• B) Syntactics
• C) Alphabets
• D) None of the given options

Two languages are said to belong to same class if they end in the same state when they run over an FA and that state ___.

• A) Must be final state
• B) May be final state or not
• C) May be start or not
• D) None of the given options