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

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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Составить грамматику
СообщениеДобавлено: 02 фев 2014, 18:08 
Не в сети
Начинающий
Зарегистрирован:
02 фев 2014, 18:00
Сообщений: 6
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый вечер. Может кто-нибудь помочь составить грамматику, порождающую формальный язык:

[math]L(G) = \left\{ (10)^{n-1}(01)^{n+1} | n>0\right\}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 02 фев 2014, 18:26 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Где Ваши попытки решения?
А для языка [math]L=\{a^nb^n, n>0\}[/math] можете грамматику составить?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 02 фев 2014, 18:33 
Не в сети
Начинающий
Зарегистрирован:
02 фев 2014, 18:00
Сообщений: 6
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Где Ваши попытки решения?
Sonic писал(а):
А для языка [math]L=\{a^nb^n, n>0\}[/math] можете грамматику составить?

Здесь вроде понятно
[math]S - aSb[/math]
[math]S - ab[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 02 фев 2014, 19:03 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Посмотрите на Ваш пример и на мой. В чем они похожи, в чем нет?
Как можно заюзать полученное решение?

Стрелка пишется так: [math]\to[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 02 фев 2014, 19:29 
Не в сети
Начинающий
Зарегистрирован:
02 фев 2014, 18:00
Сообщений: 6
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Sonic писал(а):
Посмотрите на Ваш пример и на мой. В чем они похожи, в чем нет?
Как можно заюзать полученное решение?

Я сделал примерно так, но не уверен

[math]S\to 10A01[/math]

[math]A\to A01[/math]

[math]A\to 01[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 02 фев 2014, 19:45 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Правильно, что не уверены, у Вас [math]10[/math] встретится только 1 раз, а не [math]n-1[/math]. Кроме того, если применить сначала 1-ю, а потом сразу 3-ю продукцию, то тоже получим слово не из нашего языка.

Попробуйте еще один простой пример: построить грамматику для языка [math]L=\{ab^n,n>0\}[/math]. Попытайтесь как-то скомбинировать полученные решения. Вы уже додумались использовать 2 метасимвола - это правильно. Осталось немного.

upd: хотя, у меня получилось обойтись одним метасимволом и 2-я продукциями. В качестве намека предлагаю Вам написать грамматику для языка [math]L=\{a^ncb^n,n>0\}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 02 фев 2014, 20:03 
Не в сети
Начинающий
Зарегистрирован:
02 фев 2014, 18:00
Сообщений: 6
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Sonic писал(а):
Правильно, что не уверены, у Вас [math]10[/math] встретится только 1 раз, а не [math]n-1[/math]. Кроме того, если применить сначала 1-ю, а потом сразу 3-ю продукцию, то тоже получим слово не из нашего языка.

Попробуйте еще один простой пример: построить грамматику для языка [math]L=\{ab^n,n>0\}[/math]. Попытайтесь как-то скомбинировать полученные решения. Вы уже додумались использовать 2 метасимвола - это правильно. Осталось немного.

upd: хотя, у меня получилось обойтись одним метасимволом и 2-я продукциями. В качестве намека предлагаю Вам написать грамматику для языка [math]L=\{a^ncb^n,n>0\}[/math]


А если так:

[math]S \to A0101[/math]

[math]A \to e[/math]

[math]A \to 10A01[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Составить грамматику
СообщениеДобавлено: 02 фев 2014, 20:06 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Вот, замечательно :) у меня сначала такая же была.
А потом получилась такая:
[math]S\to 10 S 01[/math]
[math]S\to 0101[/math]

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

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

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

sky2high

8

406

03 окт 2014, 14:57

Составить грамматику, порождающую формальный язык

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

genia2030

1

212

04 ноя 2017, 19:43

Составить грамматику, порождающую формальный язык

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

veronika123

1

832

07 дек 2014, 13:11

Построить автомат с магазинной памятью и КС-грамматику

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

Whiteboss

0

98

01 май 2018, 20:24

Как составить ряд

в форуме Теория вероятностей

tanyhaftv

6

53

05 ноя 2018, 13:05

Составить ЗЛП

в форуме Исследование операций и Задачи оптимизации

Petr-konev

3

273

02 июн 2014, 20:28

составить уравнение

в форуме Аналитическая геометрия и Векторная алгебра

kristish

13

455

06 дек 2011, 13:03

Как составить уравнение х1

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

AnnaLapina

7

350

17 сен 2013, 17:42

Как составить совокупности?

в форуме Математическая статистика и Эконометрика

nataliprokopovich

0

143

19 сен 2015, 19:40

Как под а) составить таблицу?

в форуме Теория вероятностей

AnnaLapina

3

255

19 сен 2013, 17:06


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



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

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


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

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

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

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