Final answer:
FA1 is a DFA for language L1 with two states representing even and odd counts of 'a's, while FA2 is a DFA for language L2 that accepts words starting with 'ba'. An NFA for L1 + L2 can be constructed based on Kleene's Theorem with an initial state branching to the starting states of FA1 and FA2 using ε-transitions.
Step-by-step explanation:
The student asked about creating finite automata (FA) for two specific languages over the alphabet Σ={a,b}. Language L1 consists of all words with an odd number of 'a's, and Language L2 consists of all words that begin with the substring 'ba'. To design FA machines for these languages, we can apply the concepts of formal language theory and automata.
FA1: Machine for L1
FA1 must accept a string if it has an odd number of 'a's. We can design a simple two-state deterministic finite automaton (DFA) where one state represents an even number of 'a's (non-accepting state) and the other represents an odd number of 'a's (accepting state). The machine changes state whenever it reads the letter 'a' and stays in the same state when it reads 'b'.
FA2: Machine for L2
For FA2, we need a DFA that accepts strings beginning with 'ba'. This requires at least a three-state DFA where the initial state transitions to a second state on input 'b', and then to an accepting state on input 'a'. Any subsequent letters after 'ba' won't affect the accepting state.
FA for L1 + L2
According to Kleene's Theorem, we can construct a machine that accepts the union of L1 and L2 by creating a non-deterministic finite automaton (NFA) that has an initial state with ε-transitions (empty string transitions) to the initial states of both FA1 and FA2. The resulting NFA can accept strings that are in L1 or L2 as per the union operation.