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

Which one of the following languages is a non regular language?

• A) Start and end with same letter
• B) Palindrome
• C) Even-even
• D) Containing double a

The basic approach of Myhill Nerode theorem is similar to the concept of:

• A) closure of FAs
• B) distinguishable and indistinguishable strings
• C) union of FAs
• D) concatenation of FAs

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

• A) regular
• B) irregular but infinite
• C) irregular but finite
• D) irregular

If an FA accepts 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

If there is no final state of two FAs then their ______ also have no _____ state

• A) final, union
• B) initial, union
• C) union, initial
• D) union,final

In CFG, symbols that cannot be replaced by anything are called __________.

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

To examine whether a certain FA accepts any words, it is required to seek the paths _______ state.

• A) from initial to initial back
• B) from initial to final
• C) from final to back final
• D) from final to initial

If a language generates finite number of distinct classes then it must be _____________.

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

If an FA has N states then it must accept the word of length

• A) N
• B) N-1
• C) 2N
• D) N+1