Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Регулярность языка
СообщениеДобавлено: 15 окт 2015, 19:15 
Не в сети
Продвинутый
Зарегистрирован:
23 окт 2014, 15:46
Сообщений: 78
Cпасибо сказано: 7
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Верно ли следующее рассуждение?
Хочу показать, что язык палиндромов - нерегулярен.
Ограничусь случаем палиндромов из 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] - нерегулярен.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Регулярность языка
СообщениеДобавлено: 15 окт 2015, 20:35 
Не в сети
Продвинутый
Зарегистрирован:
23 окт 2014, 15:46
Сообщений: 78
Cпасибо сказано: 7
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Кажется, так проще. Язык пал-ов нерегулярен, потому что содержит нерегулярный язык [math]L={ (ab)^{n} (ba)^{n} } = { x^{n} y^{n} }[/math] Это верно?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Регулярность языка
СообщениеДобавлено: 16 окт 2015, 12:52 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
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] -- слова, может быть другим.

Далее, если язык содержит нерегулярный язык, это не значит, что он сам нерегулярный. Однако идея верная: рассмотрите пересечение языка палиндромов с регулярным языком, что должно сохранять регулярность.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 3 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Как доказать сингулярность, регулярность?

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

zen

1

1360

02 фев 2019, 15:42

Доказать нерегулярность языка

в форуме Дискретная математика, Теория множеств и Логика

DanilaVladimir

0

187

07 июн 2022, 20:07

Грамматика для скобочного языка

в форуме Информатика и Компьютерные науки

tmp

8

903

06 мар 2017, 17:50

Грамматика языка логики предикатов

в форуме Дискретная математика, Теория множеств и Логика

petrowert

2

398

16 июл 2015, 12:21

Определить, для какого языка существует эквивалентный КА

в форуме Информатика и Компьютерные науки

firuzinho

0

197

16 авг 2021, 18:12

Проверить свойства контекстно свободного языка

в форуме Дискретная математика, Теория множеств и Логика

Alexander132

3

221

29 авг 2019, 05:31

Написать формулу языка арифметики утверждения

в форуме Теория чисел

plktre

4

458

14 мар 2019, 21:33

Перевести выражение с формального языка на русский

в форуме Дискретная математика, Теория множеств и Логика

ellozoid

4

574

23 июн 2014, 22:11

Построить магазинный автомат для данного языка

в форуме Дискретная математика, Теория множеств и Логика

Arius_1404

0

215

10 янв 2019, 20:34

Сколько студентов не изучают ни одного иностранного языка?

в форуме Алгебра

bibibo

0

951

05 окт 2014, 20:34


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 26


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved