TOC 1 B

Which of the following automata accepts the same set of languages as DFA?

• PDA

• Turing Machine

• NFA

• LBA

Which of the following statements is true about DFAs and NFAs?

• DFA is more powerful than NFA

• NFA is more powerful than DFA

• DFA and NFA are equally powerful

• DFA cannot accept regular languages

How many states are there in the minimum DFA accepting the language of all strings over {0,1} that end with '01'?

• 2

• 3

• 4

• 5

The main difference between DFA and NFA is:

• DFA can accept infinite languages

• NFA can have multiple transitions for the same input symbol

• DFA uses epsilon transitions

• NFA cannot accept regular languages

In an NFA, from a given state, you can go to:

• Only one next state

• No next state

• Multiple next states including zero

• Only to the initial state

Which operation cannot be performed by a DFA?

• Union

• Intersection

• Complement

• None of the above

What is ε (epsilon) in finite automata?

• A symbol in the input alphabet

• Denotes empty string transition

• Used for rejection

• Used in DFA only

What is the minimum number of states in a DFA that accepts only the string "ab"?

• 1

• 2

• 3

• 4

The language accepted by finite automata is:

• Context-free

• Context-sensitive

• Recursive

• Regular

What happens during NFA to DFA conversion?

• States increase exponentially

• New symbols are added

• States decrease

• Grammar is changed