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

If L is a regular language then ___ is also a regular language.

• A) Lm
• B) Ls
• C) Lx
• D) Lc

In large FA with thousands of states and millions of directed edges, without an effective procedure it is ________ to find a path from initial to final state.

• A) Always easy
• B) may be good
• C) always impossible
• D) Impossible

In a CFG, the non-terminals are denoted by _________.

• A) Small letters
• B) Small letters and numbers
• C) Numbers
• D) Capital letters

For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is _____________.

• A) mN
• B) Nm +Nm+1+ N m+2 +… + N2m-1
• C) mN +mN+1+ mN+2 +… +m2N-1
• D) Nm

A language ending with ‘b’ partitions ∑* into ___________distinct classes.

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

For a non-regular language, there exists ___________ FA.

• A) at least one
• B) at most one
• C) no
• D) one

Using Myhill Nerode theorem we partition sigma star into distinct __________.

• A) instances
• B) objects
• C) classes
• D) templates

Let L be any infinite regular language defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ* such that all the strings of the form xy^n z for n=1,2,3 are the words in L. This is called ___.

• A) Complement of L
• B) Pumping Lemma
• C) Kleene's theorem
• D) None in given

If an effectively solvable problem has answer in YES or NO, then the solution is called _________.

• A) decision procedure
• B) optimal procedure
• C) infinite problem
• D) finite solution

Which of the following should not be NULL in the context of Pumping Lemma?

• A) y
• B) z
• C) x
• D) n

If L1 and L2 are two regular languages, then they _______ expressed by FAs.

• A) can be
• B) May be
• C) cannot be
• D) may or may not be