Problem G
Deterministic Finite Automata - Concatenation
You are given two deterministic finite automata that accept
the languages
Input
The input contains the description of two deterministic finite automata that use the same alphabet. Each is described as follows.
The first line contains four positive integers
Each state is an integer between
Additionally it is guaranteed the total number of states in
the input is at most
Output
Output any deterministic finite automaton representing the
concatenation of the input automata. Your output is subject to
the same format and restrictions as the input, except it may be
larger, allowing
You may assume that there exists a non-deterministic finite
automata accepting
Sample Input 1 | Sample Output 1 |
---|---|
2 2 1 1 ab 1 1 2 2 2 3 2 1 1 ab 2 3 2 3 2 3 3 |
5 2 1 2 ab 3 4 2 3 2 4 5 3 5 4 5 5 |
Sample Input 2 | Sample Output 2 |
---|---|
1 4 1 0 acgt 1 1 1 1 1 4 1 1 acgt 1 1 1 1 1 |
1 4 1 0 acgt 1 1 1 1 |