Введение в схемы, автоматы и алгоритмы



             

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


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

Пример 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.


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