пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

34. Леммы о разрастании КС-языков.

Если взять достаточно длинную цепочку символов, принадлежащую произвольному КС-языку, то в ней всегда можно выделить две подцепочки, длина которых в сумме больше нуля, таких, что, повторив их сколь угодно большое число раз, можно получить новую цепочку символов, принадлежащую данному языку.

Формальная запись: Если L – это КС-язык, то $ константа p>0, pÎN ½если aÎL и ½a½³ p  , то a=bdgjm, где dj¹e, ½dgj½£ p и bdigj imÎL " i ³0.

 


19.01.2016; 06:42
хиты: 97
рейтинг:0
Точные науки
информатика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь