1’s complement for 01101 will be:

• A) 00000
• B) 00100
• C) 10010
• D) 10111

If Σ = {aa bb} then Σ* will not contain ___.

• A) aaabbb
• B) aabbbb
• C) aabbaa
• D) bbaabbbb

Closure of an FA is the same as ___________ of an FA with itself except that the initial state of the required FA is a final state as well.

• A) Concatenation
• B) Union
• C) Intersection
• D) Sum

One language can have ___ TG's.

• A) Only one
• B) Only two
• C) More than one
• D) Only three

In Moore machine the output depends on

• A) Nothing
• B) Present state and present input
• C) Only present state
• D) Type of input

According to 1st part of the Kleene's theorem if a language can be accepted by an FA then it can be accepted by a ___ as well.

• A) FA
• B) CFG
• C) GTG
• D) TG

Subtraction of binary numbers is possible through:

• A) Incrementing machine
• B) Both complementing and incrementing machine
• C) Complementing machine
• D) Converting machine

Even-palindrome is a ___ language.

• A) Non-regular
• B) Regular
• C) Regular but infinite
• D) Regular but finite

In Mealy machine the output depends on __________________

• A) Only present state
• B) Present state and Present input
• C) Type of input
• D) Nothing

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

• A) Regular
• B) Non-regular
• C) Regular but finite
• D) None of the given

While developing NFA for the union of FA1 and FA2, if there is a loop of ‘a’ at the initial state of FA1 then the new initial state will have a transition for ‘a’ that goes straight to:

• A) the initial state of FA1*FA1
• B) the final state of FA1
• C) the initial state of FA2
• D) the initial state of FA1

Pumping lemma is generally used to prove that:

• A) A given language is infinite
• B) A given language is not regular
• C) Whether two given regular expressions are equivalent or not
• D) None of these

Moore machine can have -------- final states.

• A) One
• B) More than one but infinite
• C) Zero
• D) More than one but finite

If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will ___ word/words.

• A) accept all
• B) accept no
• C) accept some
• D) reject no

In NFA having multiple transitions at certain state, FA can be built by introducing:

• A) Final state
• B) Combination of states
• C) Initial state
• D) Empty state

In CFG the symbols that can't be replaced by anything are called ___.

• A) Terminal
• B) Non-Terminal
• C) Production
• D) All of given

Strings x,y,z belongs to Σ * such that both xz or yz ∈ L where L ⊆ Σ* are:

• A) Indistinguishable
• B) Both distinguishable and indistinguishable
• C) Distinguishable
• D) Undetermined

Which of the following is a regular language?

• A) String of odd number of zeroes
• 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 these

Let L be the language of all strings, defined over Σ = {0,1}, ending in 10. Which of the following strings are indistinguishable with respect to L with z being 0?

• A) 010, 101
• B) 100, 101
• C) 111, 101
• D) 110, 101

For a given Moore Machine, the input string is '101010', thus the output string would be of length:

• A) Length of input string - 2
• B) Length of input string - 1
• C) Length of input string + 1
• D) Length of input string + 2