Ученые записки математических кафедр вып. 1970 г.

теристикой 5 ( L ) - b и. П ( ¿ ) = П ДОКАЗАТЕЛЬСТВО. Возьиеи фразу ABA в качестве Б и (В ААА) в качестве П . Тогда Z, ABA и L^{B,AAA) Пусть такой язык Z существует, дня которого Б (¿) =АВА и n(L) -{B,m) . Так как Ь(¿) и П (L) конечны, то существует КС - г р а н - натика, порождавшая язык L (теорема 3 из работы I ), гдв Г(А)=<А,В ;A’ B',np;S> S : Пр —- А'В'А' В ' — *А'А'А' . А' — -А В' - * + В’ / но Z (Г) {ABA, AAAAAJ, . Покажем, что П(С,) = ф Действительно, пусть ( А у ) ь П ( С , ) и £ ( Y ) > 1 тогда Y /MAAeZ и у может быть только равно А * что приводит к противоречию. Пусть (B.Y) € П (L) ' т о гд а * честве результ*Рувап? слов и П Щ = ф . С л ед ова тел ьн о, такого языка ^ не существует. В работе 2 доказана алгоритмическая неразрешимость ряда в оп - ®°С° В ДЛЯ М а соа КС " яэыио^ В работе I показано, что каждый «онечно характеризуемый язык может быть порожден некоторой КС- Грамматикой. Рассмотрим вопрос о конечной характеризуемое™ КС ; и быть наименьшего ранга, так , что приводит к протнворе- ' не могут быть взяты в к а - *=ААА но {ААА,В) , отсюда