Рассмотрим несколько примеров применения теоремы о разрастании.
Пример 6.4. Покажем, что язык L1 ={ w =0i 1i | i
Предположим, что он автоматный. Тогда для него имеется n из утверждения теоремы 6.3. Рассмотрим следующее ("специальное" !) слово w = 0n 1n. Очевидно, что w
Пример 6.5. Покажем, что язык СКОБ правильных скобочных последовательностей в алфавите { (, ) } не является автоматным.
Схема доказательства та же. В качестве специального слова выберем слово w = (n )n, оно, очевидно, принадлежит СКОБ. Тогда для всякого разбиения w = xyz такого, что |xy|
Пример 6.6.
Покажем, что язык L2 ={ w =0i 1j | i
Здесь, предположив, что L2 автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово w = 0{2n+1}1n
Пример 6.7. Рассмотрим язык "квадратов" в унарном алфавите { | }:
Здесь, предположив, что L3 автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово w = |{n2}. Для всякого разбиения w = xyz такого, что |xy|
Пример 6.8.
Рассмотрим язык "простых чисел" в унарном алфавите { | }:
Предположим, что Lpr - автоматный язык и зафиксируем для него константу n из теоремы 6.3.