Let be the set of letters. For a word and two languages over , we define the language as follows, by induction on .
Here, represents the empty word. For example, if , , and , then . Furthermore, for languages , we define as . For example, if , , and , then .
Answer the following questions.
(1) Let , , and . Express using a regular expression.
(2) Let , , and . Express using a regular expression.
(3) Let , , and be deterministic finite automata, and for each , let be the language accepted by . Here, are the set of states, the transition function, the initial state, and the set of final states of (), respectively. Assume that the transition functions () are total. Give a non-deterministic finite automaton that accepts , with a brief explanation. You may use -transitions.
(4) For and () in question (3), give a deterministic finite automaton that accepts , with a brief explanation.
We will construct an NFA that accepts using -transitions. The NFA will have the same structure as , but the transitions will be replaced based on the input letter with the transitions from and , and -transitions will be used to connect the states.
For example, supposing the original transitions for the input letter in are , we will replace these transitions with the corresponding transitions from :
Similarly, for the input letter , we will replace the transitions with the corresponding transitions from .
The final states of the NFA will be those states where the original final states of are reached after the substitution process.
Explanation: Since the language is obtained by substituting the strings in and for and in the strings of , the NFA needs to simulate this substitution process by transitioning to the corresponding states in and based on the input letter.
We need to track the states of , , and simultaneously.
The DFA will have states , where , , and .
The initial state is .
The transition function will be defined as:
for all .
for all .
The final states are those where the third component is a final state in .
This DFA ensures that as we read , we keep track of the corresponding states in , , and to ensure the substitution process results in strings that belong to .