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

All possible combinations of strings of a language including null string is referred as:

• A) Addition of a language with itself
• B) Subtraction of a language with itself
• C) Concatenation of a language with itself
• D) Kleene star closure of a language

The process of finding the derivation of the word generated by particular grammar is called ___.

• A) Processing
• B) Parsing
• C) Programming
• D) Planning

Keeping in view the discussion by Martin, how many states are required to recognize the language of all strings of length 2 or more defined over ∑= {a,b}, with ‘b’ being the second letter from right?

• A) 9
• B) 8
• C) 6
• D) 7

The first rule of converting the given CFG in CNF is ___.

• A) CNK algorithm
• B) CYK algorithm
• C) CKY algorithm
• D) KYC algorithm

A loop at a state is supposed to be ---------- transition while converting Moore machine into an equivalent Melay machine.

• A) Incoming
• B) Complex
• C) Outgoing
• D) Both incoming and outgoing

The language L defined over Σ, not belonging to L, is called _______ of the language L.

• A) closure
• B) intersection
• C) union
• D) complement

We cannot write regular expressions for all ___.

• A) FA's
• B) TG's
• C) NFA's
• D) CFG's

In the context of make NFA for the concatenation of FA1 and FA2 (FA2 accepting null string), which of the following option is correct?

• A) FA2 having final state only
• B) FA2 having initial state only
• C) Initial states in both FAs
• D) Final states in both FAs

For every Context Free Grammar (CFG) we can make the corresponding ___.

• A) FA
• B) TG
• C) PDA
• D) Regular Grammar

Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum ______________ number of states.

• A) more than 3
• B) None of the given options
• C) 2
• D) 3

Pumping Lemma II says that length(x) + length(y) should be ___.

• A) Less than number of states
• B) Equal to number of states
• C) Greater than number of states
• D) Greater than or equal to number of states