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

According to Myhill Nerode theorem if L generates finite no. of classes then L is ___.

• A) Finite
• B) Infinite
• C) Regular
• D) Non Regular

If the intersection of two regular languages is regular then the complement of the intersection of these two languages is also regular.

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

In pumping lemma theorem (x y^n z) the range of n is ___.

• A) n=1
• B) 2
• C) 3
• D) 4 ...

For a non regular language there exist ___ FA.

• A) One
• B) At least one
• C) At most one
• D) No

The strings or words which do not belong to a language is called ___ of that language.

• A) Intersection
• B) Union
• C) Complement
• D) Quotient

If an FA accept a word then there must exist a path from ___.

• A) Initial to final state
• B) Initial to each state
• C) Initial to each state but not to final state
• D) Initial to final state by traversing each state

FA corresponding to an NFA can be built by introducing an empty state for a letter having ___.

• A) no transition at certain state
• B) one transition at certain state
• C) two transition at certain state
• D) more than two transitions at certain state

A PDA is called nondeterministic PDA if ___.

• A) There are more than one outgoing edges at READ or POP states with one label
• B) There are more than one PUSH states
• C) There are more than one POP states
• D) All of the given options

The CFG S --> aSa | bSb | a | b | ^ represents the language ___.

• A) EVEN-EVEN
• B) PALINDROM
• C) EQUAL
• D) ODD-ODD

Halt states are ___.

• A) Start and Accept
• B) Accept and Reject
• C) Start and Reject
• D) Read and Reject

The unit and null productions can be deleted from a CFG.

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