Theory of computation

Figure 1 is the state transition table for a finite state machine (FSM). S0 is the start state and the only accepting state.

Current state	Input 0	Input 1
S0 (start, accepting)	S0	S1
S1	S1	S0

For each input string, state whether it is accepted: (a) 1101 (b) 1001 (c) 111 (d) 0000. Describe in one sentence the language the FSM accepts.

For the regular expression a(b|c)*d, state which of these strings match: ad, abcbd, abd, acdd.

State the time complexity in Big-O notation of a linear search, a binary search and a bubble sort, and explain why binary search is more efficient for large data sets.