Theory of Automata (Test 2)

What does the regular expression (a + b) match?

• One or more 'a's and 'b's
  

• Exactly one 'a' or one 'b'

• Zero or more 'a's or 'b's

• Zero or more 'a's followed by 'b'

Which of the following regular expressions matches any string that ends with 'ab'?

• a(ab)*

• (a+b)*ab

• ab(a+b)

• None of these

Which of the following regular expressions represents strings with any number of 'a's followed by exactly one 'b'?

• ab*
  

• a+b

• a*b

• b*a

The regular expression (a+b)*c represents what kind of strings?

• Strings that have only 'a's and 'b's
  
  

• Strings that contain at least one 'c'

• Strings that contain 'a', 'b', and 'c' in any order

• Strings that end with 'c'

Which of the following is a characteristic of a non-deterministic finite automaton (NFA)?

• It can be in more than one state at a time.
  
  
  

• It can have multiple transitions for the same input from a state.

• It has no start state.

• Both a) and b).

What is the main difference between a DFA and an NFA?

• A DFA has multiple states for each input symbol, while an NFA has only one.

• An NFA is always deterministic, whereas a DFA is non-deterministic.

• A DFA has a single possible transition for each input symbol from a given state, whereas an NFA can have multiple possible transitions.

• There is no difference.

Which of the following is not an essential component of a finite automaton?

• A finite set of states
  
  
  

• A tape for reading input

• An input alphabet

• A transition function

How many states are required to simulate a two-state NFA with a DFA?

• 2 states
  
  
  

• 3 states

• 4 states

• 4 or more states

In a transition table, what does each row represent?

• An input symbol
  
  
  

• A transition rule

• A state in the automaton

• A final state

What does the transition table define in the context of a DFA?

• The set of accepted strings
  
  
  

• The set of all possible state transitions for each input

• The set of non-deterministic transitions

• The start and final states