patternModerate
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
Viewed 0 times
whyregularmodlanguage
Problem
Why is $L=\{w \mid ~|w|\bmod3=\#_a(w)\bmod3\}$ a regular language?
$\#_a(w)$ is the number of $a$'s in $w$.
So far every language that I saw containing
$\#_a(w)$ is the number of $a$'s in $w$.
So far every language that I saw containing
modulo was a regular language. Can you give me an example of a non-regular language with a modulo operator in it?Solution
$\newcommand{\m}{\operatorname{\%}}$
Let $d(w)=(|w|-\#_a(w))\m3$, where $n\m 3$ is the remainder of dividing $n$ by $3$ as defined in almost every programming language.
Note $L=\{ w\mid d(w)=0\}$.
The simple and critical observation is that there are only 3 possible values for $d(w)$: $0, 1, 2$. A deterministic finite automaton (DFA) can remember and update that value for the input read so far. Accordingly, it is easy to construct a DFA that accepts $L$.
Specifically, let DFA $D$ have three states, $q_0, q_1$ and $q_2$. Here are the transitions of $D$ so that state $q_i$ accept words of $d$ value $i$.
Let $q_0$ be the start state and the only final state. Then $L$ is accepted by $D$. So $L$ is regular.
"Every language that I saw containing $\text{modulo}$ was a regular language." This is nice observation. The reason is that there is only finitely many values of $n\m d$ for an integer $n$ and a fixed integer $d$. DFAs are powerful enough to remember and update finitely many information.
However, if there are other conditions involved to define the language, it may not be regular any more.
For example, consider $N= \{a^nb^n \mid n = 0 \bmod 2\}$. $N$ is non-regular since $a^0, a^2, a^4, \cdots$ are pairwise distinguishable. For two different even number $i$ and $j$, $a^i$ and $a^j$ are distinguished by $b^i$ as $a^ib^i\in D$ but $a^jb^i\not\in D$.
Let $d(w)=(|w|-\#_a(w))\m3$, where $n\m 3$ is the remainder of dividing $n$ by $3$ as defined in almost every programming language.
Note $L=\{ w\mid d(w)=0\}$.
The simple and critical observation is that there are only 3 possible values for $d(w)$: $0, 1, 2$. A deterministic finite automaton (DFA) can remember and update that value for the input read so far. Accordingly, it is easy to construct a DFA that accepts $L$.
Specifically, let DFA $D$ have three states, $q_0, q_1$ and $q_2$. Here are the transitions of $D$ so that state $q_i$ accept words of $d$ value $i$.
- $\delta(q_i, a)= q_i$, since reading an $a$ will increase both $|\cdot|$ and $\#_a(\cdot)$ by 1.
- $\delta(q_0, x)= q_1$, $\delta(q_1, x)= q_2$, $\delta(q_2, x)= q_0$, where $x$ is any symbol that is not $a$, since reading a $x$ will increase $|\cdot|$ by 1 but keep $\#_a(\cdot)$.
Let $q_0$ be the start state and the only final state. Then $L$ is accepted by $D$. So $L$ is regular.
"Every language that I saw containing $\text{modulo}$ was a regular language." This is nice observation. The reason is that there is only finitely many values of $n\m d$ for an integer $n$ and a fixed integer $d$. DFAs are powerful enough to remember and update finitely many information.
However, if there are other conditions involved to define the language, it may not be regular any more.
For example, consider $N= \{a^nb^n \mid n = 0 \bmod 2\}$. $N$ is non-regular since $a^0, a^2, a^4, \cdots$ are pairwise distinguishable. For two different even number $i$ and $j$, $a^i$ and $a^j$ are distinguished by $b^i$ as $a^ib^i\in D$ but $a^jb^i\not\in D$.
Context
StackExchange Computer Science Q#152508, answer score: 11
Revisions (0)
No revisions yet.