129
правок
Изменения
м
1. '''Докажем, что все слова, порождённые <tex>G</tex>, есть в <tex>\overline{L}</tex>.'''
2. '''Докажем, что все слова из <tex>\overline{L}</tex> порождаются <tex>G</tex>.'''
small fixes
Докажем этот факт.
Сначала заметим, что нетерминал <tex>A</tex> порождает слова нечётной длины с центральным символом <tex>a</tex>. В свою очередь нетерминал <tex>B</tex> порождает слова нечётной длины с центральным символом <tex>b</tex>. Таким образом, правило <tex>S \to A \mid B</tex> порождает все возможные слова нечётной длины.
<tex>\varepsilon</tex>, а также все слова нечётной длины не являются тандемными повторами.
Для правила <tex>S \to BA </tex> доказательство аналогично.
С помощью <tex>G</tex> можно вывести <tex> \varepsilon</tex>, а также любое слово нечётной длины.
