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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Грамматика для скобочного языка
СообщениеДобавлено: 06 мар 2017, 18:50 
Не в сети
Начинающий
Зарегистрирован:
06 мар 2017, 18:27
Сообщений: 5
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Прошу помочь. Задача такая: Построить грамматику языка L = {[math]w \in (0,1)*[/math] | L \ (правильный скобочный язык) }, где 0 - "(", 1 - ")" то бишь язык не являющийся правильным скобочным. С первого взгляда задача казалась не трудной, но решение мне уже не приходит дня 3 в голову, а работу нужно сдавать вот уже в ближайшие сроки. Самое заковыристое слово, которое я так и не понял как обработать это "(( ))))(((( ))" , где число нулей меньше числа единиц, или наоборот. Надеюсь, что кто нибудь поможет хотя бы советом.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Грамматика для скобочного языка
СообщениеДобавлено: 06 мар 2017, 23:06 
Не в сети
Оракул
Зарегистрирован:
02 дек 2016, 23:55
Сообщений: 778
Cпасибо сказано: 47
Спасибо получено:
136 раз в 126 сообщениях
Очков репутации: 25

Добавить очки репутацииУменьшить очки репутации
Есть что-то странное в вашей фразе
tmp писал(а):
Самое заковыристое слово, которое я так и не понял как обработать это "(( ))))(((( ))" , где число нулей меньше числа единиц, или наоборот.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Грамматика для скобочного языка
СообщениеДобавлено: 07 мар 2017, 00:21 
Не в сети
Начинающий
Зарегистрирован:
06 мар 2017, 18:27
Сообщений: 5
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Правильно понимаете, про пример я имел в виду слова такого вида, [math]0_{1}...0_{i} 1_{1}...1_{j}0_{1}...0_{j} 1_{1}...1_{i}[/math] , где [math]i\ne j[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Грамматика для скобочного языка
СообщениеДобавлено: 07 мар 2017, 01:45 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1148
Cпасибо сказано: 61
Спасибо получено:
322 раз в 306 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
В статье "On Strongly Context-Free Languages" есть представление дополнения правильного скобочного языка [math]D[/math] в виде объединения двух языков, каждый из которых также выражается через [math]D[/math]. Дело в том что [math]w\in D[/math], если выполняются два условия: в любом собственном префиксе [math]w[/math] разность открывающихся и закрывающихся скобок неотрицательна, а эта разность для всего [math]w[/math] равна нулю. Отрицание этой конъюнкции и дает нужную дизъюнкцию.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
tmp
 Заголовок сообщения: Re: Грамматика для скобочного языка
СообщениеДобавлено: 07 мар 2017, 12:04 
Не в сети
Начинающий
Зарегистрирован:
06 мар 2017, 18:27
Сообщений: 5
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
3D Homer писал(а):
Отрицание этой конъюнкции и дает нужную дизъюнкцию.

Насколько я понимаю, получается, что дополнение к D так же выражается с помощью двух языков, но выполняется условие : (в любом собственном префиксе w, разность открывающих и закрывающих скобок должна быть отрицательна) \/ (та же разность во всем w не равна 0). Остается понять как реализовать это с помощью грамматики.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Грамматика для скобочного языка
СообщениеДобавлено: 07 мар 2017, 13:29 
Не в сети
Начинающий
Зарегистрирован:
06 мар 2017, 18:27
Сообщений: 5
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Хотя, ведь объединение двух не правильных скобочных языков может дать правильный, вот например из 2 нетерминалов по правилу S -> SS при выводе из левого S такого слова "((()" , а из правого S такого "()))", все ломается. Или я не до конца понял идею?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Грамматика для скобочного языка
СообщениеДобавлено: 07 мар 2017, 16:11 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1148
Cпасибо сказано: 61
Спасибо получено:
322 раз в 306 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
tmp писал(а):
Насколько я понимаю, получается, что дополнение к D так же выражается с помощью двух языков, но выполняется условие : (в любом собственном префиксе w, разность открывающих и закрывающих скобок должна быть отрицательна)
В некотором собственном префиксе.

tmp писал(а):
Хотя, ведь объединение двух не правильных скобочных языков может дать правильный, вот например из 2 нетерминалов по правилу S -> SS при выводе из левого S такого слова "((()" , а из правого S такого "()))", все ломается.
Я не до конца понял структуру вашего предложения ("при выходе такого слова" что?). Возможно, вы путаете объединение и конкатенацию.

Обозначим через [math][w][/math] разность количества ( и ) в [math]w[/math]. Тогда [math]w\in D[/math] тогда и только тогда, когда [math][u]\ge0[/math] для любого префикса [math]u[/math] слова [math]w[/math] и [math][w]=0[/math]. Соответственно, [math]w\notin D[/math] тогда и только тогда, когда [math][u]<0[/math] для некоторого префикса [math]u[/math] или [math][w]\ne0[/math]. Второе условие можно заменить на [math][w]>0[/math], т.к. случай [math][w]<0[/math] покрывается первым условием.

Если [math][u']<0[/math] для некоторого префикса [math]u'[/math], то найдутся такие [math]u[/math], [math]v[/math], что [math][u]=0[/math] и [math]w=u)v[/math]. Обратное также верно. Если же [math][w]>0[/math], то найдутся такие [math]u[/math], [math]v[/math], что [math][v]=0[/math] и [math]w=u(v[/math]. Здесь обратное неверно, но любое слово такого вида все равно не входит в [math]D[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
tmp
 Заголовок сообщения: Re: Грамматика для скобочного языка
СообщениеДобавлено: 08 мар 2017, 19:26 
Не в сети
Начинающий
Зарегистрирован:
06 мар 2017, 18:27
Сообщений: 5
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Спасибо, я понял. А в примере со словом была ошибка. Вот что получилось в итоге:
S -> A | B
A -> C ) G
C -> ( C ) | CC | e
G -> ( G | ) G | e
B -> G ( K
K -> ( K ) | KK | e
где e - эпсилон
Нетерминал A выводит слово по условию: [math][u'] < 0[/math] для некоторого префикса u'.
Нетерминал B выводит слово по условию: [math][w] > 0[/math]
Правило A -> C ) G соответствует w = u)v
Из С выводится правильная скобочная последовательность, а из G любая последовательность, потому как не важно что будет
справа от ). Дальше для B по аналогии. Надеюсь нигде не ошибся.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Грамматика для скобочного языка
СообщениеДобавлено: 08 мар 2017, 20:47 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1148
Cпасибо сказано: 61
Спасибо получено:
322 раз в 306 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
Согласен. Вместо K можно использовать C, а A и B — это нетерминалы.

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Грамматика языка логики предикатов

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

petrowert

2

184

16 июл 2015, 13:21

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

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

Stasya7

2

222

15 окт 2015, 20:15

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

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

ellozoid

4

197

23 июн 2014, 23:11

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

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

Dragon_War

1

336

09 ноя 2013, 09:56

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

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

bibibo

0

492

05 окт 2014, 21:34

Переведите с естественного языка на язык логики предикатов

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

art33

5

303

20 фев 2016, 05:16


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



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

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


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

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

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

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