Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 3 ] |
|
Автор | Сообщение | |
---|---|---|
Stasya7 |
|
|
Хочу показать, что язык палиндромов - нерегулярен. Ограничусь случаем палиндромов из 2 букв. Язык палиндромов есть объединение двух языков [math]L=L_{1} \lor L_{2}[/math], где [math]L_{1}[/math] - палиндромы четной длины, а [math]L_{2}[/math] - нечетной. Достаточно показать, что хотя бы один из языков [math]L_{1}[/math] или [math]L_{2}[/math] - нерегулярен для нерегулярности всего [math]L[/math] Для четной длины: все слова состоят из пар типа [math]aba...aba[/math]. Будем заменять каждый "дубль" [math]X_{i}X_{n-i+1 } , i=1..\frac{ n }{ 2 }[/math] на пару [math]a_{i}b_{n-i+1}[/math]. В итоге получим слова типа [math]aaa...bbb[/math]. А язык [math]L'={a^{n}b^{n}[/math] - нерегулярен. Значит, [math]L_{1}[/math] - нерегулярен и, следовательно, [math]L[/math] - нерегулярен. |
||
Вернуться к началу | ||
Stasya7 |
|
|
Кажется, так проще. Язык пал-ов нерегулярен, потому что содержит нерегулярный язык [math]L={ (ab)^{n} (ba)^{n} } = { x^{n} y^{n} }[/math] Это верно?
|
||
Вернуться к началу | ||
3D Homer |
|
|
Stasya7 писал(а): Ограничусь случаем палиндромов из 2 букв. Я сначала подумал, что вы рассматриваете палиндромы длины 2. Stasya7 писал(а): Язык палиндромов есть объединение двух языков [math]L=L_{1}\lor L_{2}[/math] Объединение пишется [math]L_{1}\cup L_{2}[/math].Stasya7 писал(а): Достаточно показать, что хотя бы один из языков [math]L_{1}[/math] или [math]L_{2}[/math] - нерегулярен для нерегулярности всего [math]L[/math]. Этого действительно достаточно, но в общем случае если [math]L=L_1\cup L_2[/math] и [math]L_1[/math] не регулярный, то отсюда не следует, что [math]L[/math] не регулярный. Не следует даже в случае, когда [math]L_1\cap L_2=\emptyset[/math]. Возьмите нерегулярный язык [math]L_1[/math] и его дополнение в качестве [math]L_2[/math].Stasya7 писал(а): Для четной длины: все слова состоят из пар типа [math]aba...aba[/math]. Это слишком неконкретно.Stasya7 писал(а): Будем заменять каждый "дубль" [math]X_{i}X_{n-i+1}[/math] , [math]i=1..\frac{n}{2}[/math] на пару [math]a_{i}b_{n-i+1}[/math] Вы должны доказать, что при таких заменах регулярный язык не может стать нерегулярным.Stasya7 писал(а): Язык пал-ов нерегулярен, потому что содержит нерегулярный язык L={ (ab)^{n} (ba)^{n} } = { x^{n} y^{n} } Что имеется в виду под x и y? Обычно это индивидуальные символы, а не слова. Доказательство, что [math]x^ny^n[/math] нерегулярный, где [math]x[/math] и [math]y[/math] -- слова, может быть другим.Далее, если язык содержит нерегулярный язык, это не значит, что он сам нерегулярный. Однако идея верная: рассмотрите пересечение языка палиндромов с регулярным языком, что должно сохранять регулярность. |
||
Вернуться к началу | ||
[ Сообщений: 3 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Как доказать сингулярность, регулярность?
в форуме Функциональный анализ, Топология и Дифференциальная геометрия |
1 |
1360 |
02 фев 2019, 15:42 |
|
Доказать нерегулярность языка | 0 |
187 |
07 июн 2022, 20:07 |
|
Грамматика для скобочного языка
в форуме Информатика и Компьютерные науки |
8 |
903 |
06 мар 2017, 17:50 |
|
Грамматика языка логики предикатов | 2 |
398 |
16 июл 2015, 12:21 |
|
Определить, для какого языка существует эквивалентный КА
в форуме Информатика и Компьютерные науки |
0 |
197 |
16 авг 2021, 18:12 |
|
Проверить свойства контекстно свободного языка | 3 |
221 |
29 авг 2019, 05:31 |
|
Написать формулу языка арифметики утверждения
в форуме Теория чисел |
4 |
458 |
14 мар 2019, 21:33 |
|
Перевести выражение с формального языка на русский | 4 |
574 |
23 июн 2014, 22:11 |
|
Построить магазинный автомат для данного языка | 0 |
215 |
10 янв 2019, 20:34 |
|
Сколько студентов не изучают ни одного иностранного языка?
в форуме Алгебра |
0 |
951 |
05 окт 2014, 20:34 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 26 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |