Question

Let ${\mathbf{M}}_{\mathbf{1}}$and${\mathbf{M}}_{\mathbf{2}}$ be DFAs that have ${\mathit{k}}_{\mathbf{1}}$ and ${\mathit{k}}_{\mathbf{2}}$states, respectively, and then let $\mathbf{U}\mathbf{=}\mathbf{L}\mathbf{\left(}{\mathbf{M}}_{\mathbf{1}}\mathbf{\right)}\mathbf{\cup }\mathbf{L}\mathbf{\left(}{\mathbf{M}}_{\mathbf{2}}\mathbf{\right)}$ .

1. Show that if $\mathbf{U}\mathbf{\ne }\mathbf{\varphi }$, then $\mathbf{U}$ contains some string $\mathbf{s}$, where $\mathbf{\left|}\mathbf{s}\mathbf{\right|}\mathbf{<}\mathbf{max}\mathbf{(}{\mathbf{k}}_{\mathbf{1}}\mathbf{,}{\mathbf{k}}_{\mathbf{2}}\mathbf{)}$ .
2. Show that if $\mathbf{U}\mathbf{\ne }\mathbf{\sum }\mathbf{*}$, then $\mathbf{U}$excludes some string $\mathit{s}$ , where $\mathbf{\left|}\mathbf{s}\mathbf{\right|}\mathbf{<}{\mathbf{k}}_{\mathbf{1}}{\mathbf{k}}_{\mathbf{2}}$ .

Short answer

1. It can be shown that , if $\mathrm{U}\ne \mathrm{\varphi }$, then $\mathrm{U}$ contains some string $\mathrm{s}$, where $\left|\mathrm{s}\right|<\max ({\mathrm{k}}_1,{\mathrm{k}}_2)$.
2. It can be shown that if $\mathrm{U}\ne \sum *$, then $\mathrm{U}$excludes some string $\mathrm{s}$ , where $\left|\mathrm{s}\right|<{\mathrm{k}}_1{\mathrm{k}}_2$.

Step-by-step solution

Explain DFA

Deterministic Finite Automata is a machine that has a finite number of states. It has the knowledge about which state, the machine moves on getting the input symbol.

Show that if  U≠ϕ, then  U  contains some string s , where  |s|<max(k1,k2) .

a.

Given that the ${\mathrm{M}}_1$ and ${\mathrm{M}}_2$ are the DFAs, that have ${\mathrm{K}}_1$ and ${\mathrm{K}}_2$ states respectively. Then consider that, $\mathrm{U}=\mathrm{L}\left({\mathrm{M}}_1\right)\cup \mathrm{L}\left({\mathrm{M}}_2\right)$ , and the DFAs consists of unequal length strings that are different from each other.

For the given grammar $\mathrm{U}$ , the start state $\mathrm{q}$ is considered. The production of ${\mathrm{M}}_1$ and ${\mathrm{M}}_2$ is, $\mathrm{q}\to {\mathrm{sM}}_1|{\mathrm{sM}}_2$.The strings that has unequal length and different from each other, are initiated for the grammar. The property of Union, add the unmatched longest string of the two strings.

Therefore, the final string is less than any string and thus, it has been shown that if $\mathrm{U}\ne \mathrm{\varphi }$, then $\mathrm{U}$contains some string$\mathrm{s}$ , where$\left|\mathrm{s}\right|<\max ({\mathrm{k}}_1,{\mathrm{k}}_2)$ .

Show that if U≠∑*, then U  excludes some string s  , where |s|<k1k2 .

b.

Given that the ${\mathrm{M}}_1$ and $M_2$ are the DFAs, that have ${\mathrm{k}}_1$ and ${\mathrm{k}}_2$ states respectively. Then consider that, $\mathrm{U}=\mathrm{L}\left({\mathrm{M}}_1\right)\cup \mathrm{L}\left({\mathrm{M}}_2\right)$ , and the DFAs consist of unequal-length strings that are different from each other.

Consider that $\mathrm{U}=\mathrm{L}\left({\mathrm{M}}_1\right)\cup \mathrm{L}\left({\mathrm{M}}_2\right)$ , that consists the string of ${\mathrm{M}}_1$ and ${\mathrm{M}}_2$. Apply the concatenation operation between the initial string ${\mathrm{k}}_1$ and ${\mathrm{k}}_2$ , then the length of the string is longer than the original length. In the final concatenated string, some strings have been taken. Hence, these strings are excluded in the final string.

Therefore, from the above discussion it has been concluded that if $\mathrm{U}\ne \sum *$, then $\mathrm{U}$excludes some string $\mathrm{s}$ , where$\left|\mathrm{s}\right|<{\mathrm{k}}_1{\mathrm{k}}_2$ .