P24MS905-Finite Automata and Regular Languages

The language accepted by an NFA is which of the following?

• Always different from a DFA

• Always non-regular

• The same as a DFA

• None of the above

Which property is not true for Regular Languages?

• Closed under palindrome formation

• Closed under complementation

• Closed under intersection

• Closed under union

Which of the following is true for Deterministic Finite Automata (DFA)?

• DFA has a unique transition for each symbol from every state

• DFA cannot recognize regular languages

• DFA can have multiple transitions for the same symbol from a state

• DFA can have epsilon transitions

The Pumping Lemma states that for any Regular Language L, there exists a constant p such that any string in L of length at least p can be written as -------.

• xyz where |y| > p

• xyz where |x| > p

• xyz where y can be repeated any number of times

• xyz where |z| > p

What is the Kleene closure of a language L?

• Reverse of L

• Infinite concatenation of L with itself

• Set of all suffixes of L

• Set of all prefixes of L

If a Regular Language is complemented, the result is --------.

• Always context-free

• Sometimes regular

• Never regular

• Always regular

A Non-Deterministic Finite Automaton (NFA) differs from a DFA because --------.

• NFA allows multiple transitions for the same input

• NFA cannot recognize regular languages

• NFA always requires an epsilon transition

• NFA uses more states than DFA

Which of the following is true about epsilon (ε) transitions in NFAs?

• Epsilon transitions consume input symbols

• Epsilon transitions do not change the state

• Epsilon transitions allow state transitions without reading input

• Epsilon transitions make NFA less powerful than DFA

The language L = {w | w contains at least one 'a'} is recognized by -------.

• A DFA with one state

• A DFA with two states

• An NFA with infinite states

• None of the above

Which normal form is used for simplifying CFGs?

• Turing Normal Form

• Pushdown Normal Form

• Chomsky Normal Form (CNF)

• Greibach Normal Form