Примеры неавтоматных языков

Рассмотрим несколько примеров применения теоремы о разрастании.

Пример 6.4. Покажем, что язык L1 ={ w =0i 1i | i

1 } не является автоматным.

Предположим, что он автоматный. Тогда для него имеется n из утверждения теоремы 6.3. Рассмотрим следующее ("специальное" !) слово w = 0n 1n. Очевидно, что w

L1. Предположим, что существует разбиение w = xyz, удовлетворяющего условиям (1) и (2) теоремы. Так как по условию (2) |xy|

n, то y = 0i для некоторого i>0. Но тогда слово w0 = xz= 0n-i1n

L1, что противоречит условию (3) теоремы. Следовательно язык L1 не автоматный.

Пример 6.5. Покажем, что язык СКОБ правильных скобочных последовательностей в алфавите { (, ) } не является автоматным.

Схема доказательства та же. В качестве специального слова выберем слово w = (n )n, оно, очевидно, принадлежит СКОБ. Тогда для всякого разбиения w = xyz такого, что |xy|

n слово y = (i для некоторого i>0. И, как и в предыдущем примере, слово w0 = xz= (n-i)n

СКОБ, что противоречит условию (3) теоремы. Следовательно, язык СКОБ не автоматный.

Пример 6.6.

Покажем, что язык L2 ={ w =0i 1j | i

2j+1 } не является автоматным.

Здесь, предположив, что L2 автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово w = 0{2n+1}1n

L2. Для всякого разбиения w = xyz такого, что |xy|

n слово y = 0i для некоторого i>0. Рассмотрим слово w2 = x y2 z = 0{2n+1+i}1n. Но

$2n+1+i \geq 2n+2 \not\leq 2n+1$

. Следовательно, w2

L2 и язык L2 не является автоматным.

Пример 6.7. Рассмотрим язык "квадратов" в унарном алфавите { | }:

$L_3 =\{ |^{i^2}\ |\ i \geq 0 \}$

Здесь, предположив, что L3 автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово w = |{n2}. Для всякого разбиения w = xyz такого, что |xy|

n слово y = |i для некоторого 0 < i

n. Тогда

$w_0= xz = |^{n^2 - i}$

. Но n2 - i

n2 -n > n2 -2n +1 =(n-1)2. Следовательно, n2 - i не является полным квадратом и w0

L3, т.е. язык "квадратов" L3 не является автоматным.

Пример 6.8.

Рассмотрим язык "простых чисел" в унарном алфавите { | }:

$L_{pr} =\{ |^{p}\ |\ p - \textit{ простое число } \}$

Предположим, что Lpr - автоматный язык и зафиксируем для него константу n из теоремы 6.3.

Содержание Назад Вперед