Question

Consider the following two languages over the alphabet Σ = {a, b}: L1 is the language of all words with an odd number of a’s and L2 is the language of all words that begins with the substring ba. a) Using the trial and effort method we demonstrated in lecture, draw FA1 : a machine that L1 and FA2 : a machine that accepts L2 .

Answer 1

To draw an FA1 machine that accepts language L1, use an NFA with two states and a loop labeled 'a'. To draw an FA2 machine that accepts language L2, use a DFA with three states and transitions labeled 'b' and 'a'.

Step-by-step explanation:

To draw an FA1 machine that accepts language L1, which consists of all words with an odd number of 'a's, we can use a non-deterministic finite automaton (NFA). This NFA has two states: State 0 and State 1. State 0 is the start state and also an accepting state. From State 0, there is a transition labeled 'a' to State 1. From State 1, there is a loop labeled 'a' back to State 1. This loop allows the NFA to accept any number of 'a's.

To draw an FA2 machine that accepts language L2, which consists of all words that begin with the substring 'ba', we can use a deterministic finite automaton (DFA). This DFA has three states: Start State, State 1, and State 2. The Start State is the start state and an accepting state. From the Start State, there is a transition labeled 'b' to State 1. From State 1, there is a transition labeled 'a' to State 2. This DFA ensures that any word that begins with 'ba' is accepted.