オートマトン 言語理論 計算論 I [第2版]の4章にある正則言語の問題（原著の解答ページには載っていないもの）の解答です．過去に同じ問題を院試過去問で見たことがあり，最近ふと読み直して考えてみたら簡単にできたので書いておきます．
正則言語を正規言語と呼ぶこともあるようですが，ここでは正則言語で統一します．
（初投稿なので練習も兼ねています）
使うのは以下の有限オートマトンに対する反復補題のみです．
反復補題
任意の正則言語 $L$ に対し定数 $N_L\geq 1$ が存在し，$|w|\geq N_L$ なる任意の $w\in L$ は，次を満たす $3$ つの部分文字列の連接 $w=xyz$ に分割できる．
$(1)$ $y\neq\varepsilon$
$(2)$ $|xy|\leq N_L$
$(3)$ 任意の $k\geq 0$ に対し $xy^kz\in L$
2進数として見た時素数となる文字列の集合
$L_1:=\{ w\in \{0,1\}^{\ast}; w$ は $2$ 進数として見た時素数である$\}$ は正則言語でない． (P.144 問4.1.3 (a))
(証明) $L_1$ が正則言語であったとして，$N$ を補題の定数とする．素数は無限に存在するから， $p\in L_1$ であって $|p|\geq 2N$ となるものが存在する．
このとき補題による $p$ の分割を $p=xyz$ とすると $q:=xy^p z\in L_1$ であり， $p\geq 2$ より $q>p$ である．
$y\neq \varepsilon$ より $2^{|y|}-1>0.$ また， $|p|\geq 2N, |y|\leq |xy|\leq N$ より
p-(2^{|y|}-1)\geq 2^{2N-1}-(2^N-1)=2^N (2^{N-1}-1)+1>0.
よって $0<2^{|y|}-1<p$ である．
以下 $\bmod p$ とする．$2^{|y|}-1\not\equiv 0$ であることに注意し，$q$ を文字列ではなく数値として見ると
\begin{align}
q&=2^{p|y|+|z|}x+2^{(p-1)|y|+|z|}y+\cdots+2^{|z|}y+z\\
&=2^{p|y|+|z|}x+\frac{2^{p|y|}-1}{2^{|y|}-1}2^{|z|}y+z\\
&\equiv 2^{|y|+|z|}x+\frac{2^{|y|}-1}{2^{|y|}-1}2^{|z|}y+z \quad (\because \text{Fermat の小定理})\\
&=2^{|y|+|z|}x+2^{|z|}y+z\\
&=p\equiv 0.
\end{align}
よって $q$ は素数 $p$ の倍数だが，$q>p$ より $q$ は合成数．これは $q\in L_1$ に矛盾．
0と1の個数が互いに素となる文字列の集合
$L_2=\{ 0^i 1^j; \gcd(i,j)=1\}$ は正則言語でない． (P.144 問4.1.3 (b))
(証明) $L_2$ が正則言語であったとし，$N$ を補題でいう定数とする．$p>N$ となる素数を取ると $\gcd(p, p+1)=1$ より $w:=0^{p+1}1^p \in L_2.$
補題による $w$ の分割を $w=xyz$ とすると， $p>N$ より $x,y$ は $0$ のみからなるので，
x=0^m, y=0^n, z=0^{p+1-m-n}1^p \quad (m+n\leq N, n>0)
と書ける．
今 $n\leq m+n \leq N < p$ だから $\gcd(n, p)=1.$ よって $(a, b)\in \mathbb{Z}^2$ であって $an+bp=1$ となるものが取れる．$(a, b)$ がこれを満たすなら 任意の $k\in \mathbb{Z}$ に対し $(a+kp, b-kn)$ も満たすから，$a>0$として良い．
補題により $w_k := xy^{k}z=0^{p+1+(k-1)n}1^p \in L_2$ であるが，$k=1+(p-1)a$ の時
\begin{align}
p+1+(k-1)n
=p+1+(p-1)an
\equiv 1-an
=bp
\equiv 0 \quad \bmod p
\end{align}
となって $\gcd(p+1+(k-1)n, p)=p>N\geq 1$ で $w_k\in L_2$ に矛盾．