The production of the form: nonterminal to one nonterminal is called the ___.

• A) Unit production
• B) NULL production
• C) Terminal production
• D) Non Terminal production

Prime is a ______________ language.

• A) finite
• B) regular
• C) both context free and regular
• D) non-regular

If Q = {xx, xyxxxy }, and R = {xyxyxyxxyy, xyxyyyxx} then Pref( Q in R) = ____________

• A) xyxyyy
• B) xx
• C) xxy
• D) xyxyxy

The operators like (* , +) in the parse tree are considered as ________.

• A) productions
• B) terminals
• C) non-terminals
• D) intermediates

A non regular language can be represented by

• A) None of the given options
• B) FA
• C) TG
• D) RE

Which of the following cannot be represented by a regular expression?

• A) String of 0’s with a prime length
• B) Language of even-even
• C) String of 0’s with an odd length
• D) Language of odd-odd

Even-Even language partitions ∑* into ___________ distinct classes.

• A) two
• B) five
• C) four
• D) three

The language of all strings not beginning with ‘b’ partitions ∑* into ___________distinct classes.

• A) four
• B) two
• C) five
• D) three

The production S --> SS | a | b | ^ can be expressed by Regular expression _________.

• A) (ab)*
• B) (a+b)
• C) (a+b)*
• D) (a+b)+

The grammatical rules which involve meaning of words are called ___________.

• A) strings
• B) alphabets
• C) semantics
• D) syntactics

CFG stands for ___.

• A) Context Free Graph
• B) Context Free Grammar
• C) Context Finite Graph
• D) Context Finite Grammar

The CFG S → aSb|ab|Λ is used to express the language _________.

• A) Palindrome
• B) Prime
• C) Even
• D) Equal

Incase of Myhill Nerode theorem, if a language L partitions sigma star into distinct classes and L is also regular then L generates ___________ number of classes.

• A) specified
• B) odd
• C) infinite
• D) finite

A problem that has decision procedure is called _________ problem.

• A) Regular language
• B) un-decidable
• C) Infinite
• D) decidable

A ___ operator adds a new letter at the top of STACK.

• A) PUSH
• B) POP
• C) READ
• D) APPEND

Which of the following is not a true theorem?

• A) Equivalency theorem
• B) Pseudo theorem
• C) Myhill Nerode theorem
• D) Decidability theorem

PDA stands for ___.

• A) Push and Drop Automaton
• B) Pop and Drop Automaton
• C) Push Down Automaton
• D) None of given options

In polish notation, (o-o-o) is the abbreviation of _________.

• A) Operand - Operator – Operand
• B) Operator - Operand – Operand
• C) Operand - Operand – Operand
• D) Operand - Operand - Operator

The production of the form: Nonterminal to ^ is said to be ___ production.

• A) NULL
• B) UNIT
• C) Chomsky form production
• D) None of the given options

The language “PRIME” is an example of ________ language.

• A) non regular
• B) non regular but finite
• C) regular but finite
• D) regular