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

An alphabet of Σ is valid if ___.

• A) No letter of Σ appears in middle of any other letter
• B) No letter of Σ appears at end of any other letter
• C) No letter of Σ appears at start of any other letter
• D) No letter of Σ appears at end or middle of any other letter

Which of the following represent the absence and presence of current in sequential circuit respectively?

• A) 1, 1
• B) 1, 0
• C) 0, 1
• D) 0, 0

Let FA1 has x number of states and FA2 has y number of states. Now FA1+FA2 can have maximum _______________ number of states.

• A) x/y
• B) None of the given options
• C) x+y
• D) x-y

If a CFG has only productions of the form nonterminal to string of two nonterminals or nonterminal to one terminal, then the CFG is said to be in ___.

• A) Chomsky Normal Form
• B) Ambiguous Form
• C) Left Aligned Form
• D) Right Aligned Form

The values of input (say a & b) do not remain same in one cycle due to

• A) OR gate
• B) Clock pulse
• C) NAND gate
• D) NOT gate

We can also represent an FA using different states. The ___ state behaves as final state of an FA.

• A) Accept
• B) Pop
• C) Push
• D) Reject

If FA1 corresponds to (a+b)* then FA1 must accept ___________ string/strings.

• A) Every
• B) Even length
• C) Odd length
• D) No

Where the input string is placed before it is run is called ___.

• A) Date tape
• B) Input Tape
• C) Output Tape
• D) Magnetic tape

There may be more than one transition for a certain letter on a state in:

• A) Transition Table
• B) Moore Machine
• C) Non-Deterministic Finite Automata
• D) Finite Automata