Let L be the language defined over the alphabet 0 1 such that the words in L do not contain 11' as a substringbuild the deterministic Finite Automata for the language L?

Answer 1

To construct a deterministic finite automaton (DFA) for the language L that does not contain the substring "11", we can define three states:

1. q0 (start state): Accepting state, where we haven't seen any '1's.
2. q1: State where we've seen a single '1'; if we see another '1', we transition to a non-accepting dead state.
3. q2 (dead state): Non-accepting state where we've seen "11".

The transitions are defined as follows:

• From q0, on input '0', stay in q0; on input '1', transition to q1.
• From q1, on input '0', return to q0; on input '1', transition to q2.
• From q2, on both '0' and '1', remain in q2 (dead state).

This DFA effectively rejects any string containing "11".