Question

1. Construct a DFA that accepts sets of all strings over {0,1}

of length 2.

2. Construct a DFA that accepts sets of all strings over {0,1}

that start with ‘0’.

3. Construct a DFA that recognises balanced sequences of

parenthesis with a maximal nesting depth of 3, e.g., ε, ()(),

(()(())) or (()())()() but not (((()))) or (()(()(())

Answer 1

To construct a DFA accepting strings over {0,1} of length 2, create a DFA with two states. For strings starting with '0', use a DFA with two states. To recognize balanced sequences of parenthesis with a nesting depth of 3, create a DFA with four states.

Step-by-step explanation:

Question 1: Construct a DFA that accepts sets of all strings over {0,1} of length 2.

To construct a DFA that accepts sets of all strings over {0,1} of length 2, we can have two states in the DFA. The starting state will be the initial state, and we can directly transition to the accepting state after reading two symbols. For example, the DFA can have the following transition table:

Current StateSymbolNext Stateq00 or 1q1q10 or 1Accepting state

Question 2: Construct a DFA that accepts sets of all strings over {0,1} that start with '0'.

To construct a DFA that accepts sets of all strings over {0,1} that start with '0', we can have two states in the DFA. The initial state will be the starting state, and if the first symbol is '0', we transition to the accepting state. If the first symbol is '1', we transition back to the initial state. For example, the DFA can have the following transition table:

Current StateSymbolNext Stateq00Accepting stateq01q0

Question 3: Construct a DFA that recognises balanced sequences of parenthesis with a maximal nesting depth of 3.

To construct a DFA that recognizes balanced sequences of parenthesis with a maximal nesting depth of 3, we can have four states in the DFA. The initial state will be the starting state, and we will increment the nesting depth each time we encounter '('. If at any point the nesting depth exceeds 3, then we transition to a non-accepting state. We transition to the accepting states when the nesting depth goes back to 0. For example, the DFA can have the following transition table:

Current StateSymbolNext Stateq0(q1q0)Invalid stateq1(q2q1)q0q2(q3q2)q1q3(Invalid stateq3)q2