patternMinor
Complement of language $\{ x \in \{a,b,c,d\}^* : \exists$ prefix $y$ of $x$ such that $||y|_a - |y|_b|\leq 10 \}$
Viewed 0 times
suchprefixlanguagethatexistscomplementleq
Problem
Is the complement of the following language a regular language?
$$L = \{ x \in \{a,b,c,d\}^* : \exists \text{ prefix }y\text{ of }x\text{ such that }||y|_a - |y|_b|\leq 10 \}$$
My first thought is that it is not a regular language because finite automata can't store the number of $a$ in $x$ and the number of $b$ in $x$, but I guess I do not understand what is the meaning of the prefix here. Could someone help me?
$$L = \{ x \in \{a,b,c,d\}^* : \exists \text{ prefix }y\text{ of }x\text{ such that }||y|_a - |y|_b|\leq 10 \}$$
My first thought is that it is not a regular language because finite automata can't store the number of $a$ in $x$ and the number of $b$ in $x$, but I guess I do not understand what is the meaning of the prefix here. Could someone help me?
Solution
First of all, a language is regular iff its complement is regular. Therefore it suffices to determine whether $L$ itself is regular.
Indeed, since $\epsilon$ is a prefix of every word, and $\epsilon$ satisfies $||\epsilon|_a-|\epsilon|_b| \leq 10$, we see that $L = \Sigma^*$, and in particular $L$ is regular.
Matters become more interesting if we replace the condition $||y|_a-|y|_b| \leq 10$ by its complement $||y|_a-|y|_b| > 10$. In this case the language $L$ is still regular, but the argument is a bit more complicated. Let us show that the following language is regular:
$$
L' = \{ x \in \{a,b,c,d\}^* : \text{some prefix $y$ of $x$ satisfies $||y|_a-|y|_b| > 10$}\}.
$$
(Its complement is the language of all words, all of whose prefixes satisfy $||y|_a-|y|_b| \leq 10$.)
We construct a DFA with 22 states $\{q_{-10},\ldots,q_{+10},q_f\}$. The initial state is $q_0$, and the unique final state is $q_f$. The transition function is given by the following table:
$$
\begin{array}{c|cccc}
q & \delta(q,a) & \delta(q,b) & \delta(q,c) & \delta(q,d) \\\hline
q_{-10} & q_{-9} & q_f & q_{-10} & q_{-10} \\
q_{-9} & q_{-8} & q_{-10} & q_{-9} & q_{-9} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
q_9 & q_{10} & q_8 & q_9 & q_9 \\
q_{10} & q_f & q_9 & q_{10} & q_{10} \\
q_f & q_f & q_f & q_f & q_f
\end{array}
$$
If the current prefix satisfies $||y|_a-|y|_b| > 10$, the DFA moves to state $q_f$ and stays there. Otherwise, the DFA is in state $q_i$, where $i = |y|_a - |y|_b$.
Indeed, since $\epsilon$ is a prefix of every word, and $\epsilon$ satisfies $||\epsilon|_a-|\epsilon|_b| \leq 10$, we see that $L = \Sigma^*$, and in particular $L$ is regular.
Matters become more interesting if we replace the condition $||y|_a-|y|_b| \leq 10$ by its complement $||y|_a-|y|_b| > 10$. In this case the language $L$ is still regular, but the argument is a bit more complicated. Let us show that the following language is regular:
$$
L' = \{ x \in \{a,b,c,d\}^* : \text{some prefix $y$ of $x$ satisfies $||y|_a-|y|_b| > 10$}\}.
$$
(Its complement is the language of all words, all of whose prefixes satisfy $||y|_a-|y|_b| \leq 10$.)
We construct a DFA with 22 states $\{q_{-10},\ldots,q_{+10},q_f\}$. The initial state is $q_0$, and the unique final state is $q_f$. The transition function is given by the following table:
$$
\begin{array}{c|cccc}
q & \delta(q,a) & \delta(q,b) & \delta(q,c) & \delta(q,d) \\\hline
q_{-10} & q_{-9} & q_f & q_{-10} & q_{-10} \\
q_{-9} & q_{-8} & q_{-10} & q_{-9} & q_{-9} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
q_9 & q_{10} & q_8 & q_9 & q_9 \\
q_{10} & q_f & q_9 & q_{10} & q_{10} \\
q_f & q_f & q_f & q_f & q_f
\end{array}
$$
If the current prefix satisfies $||y|_a-|y|_b| > 10$, the DFA moves to state $q_f$ and stays there. Otherwise, the DFA is in state $q_i$, where $i = |y|_a - |y|_b$.
Context
StackExchange Computer Science Q#110099, answer score: 4
Revisions (0)
No revisions yet.