Форум программистов, компьютерный форум, киберфорум
Наши страницы
Теория автоматов
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
1

Построить язык, порожденный такой грамматикой. Определить тип грамматики

30.10.2016, 22:15. Просмотров 940. Ответов 24
Метки нет (Все метки)

Дано грамматику G = (V, T, S, P), где , V={0, 1, S, A, B}, T={0,1}, http://www.cyberforum.ru/cgi-bin/latex.cgi?P = {{S\rightarrow 0S, A\rightarrow A1, S\rightarrow A, A\rightarrow \Lambda }}, s - начальный символ. Построить язык, порожденный такой грамматикой. Определить тип грамматики.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.10.2016, 22:15
Ответы с готовыми решениями:

Построить язык, порожденный такой грамматикой
Дано грамматику G=(V, T, S, P), де V={0, 1, S, A, B}, T={0,1}, P={S->0A, S->A, S->0, A->1} s...

Построить недетерминированный конечный автомат, допускающий язык, порожденный данной грамматикой
Дано грамматику G = (V, T, S, P), где V = {0, 1, S, A, B}, T = {0,1}, S - начальный символ....

Найти язык, порожденный грамматикой
Здравствуйте. Можете объяснить пошагово как решать данную задачу, примеров нигде толком нет:

Найти язык, порожденный грамматикой
Пусть V=\left, T=\left. Найти язык, порожденный грамматикой G=\left с таким множеством продукций Р:...

Определить тип грамматики и язык, который порождает грамматика
Дана следующая грамматика: G = ({S, {L}_{a}, {L}_{b}, {R}_{a}, {R}_{b}, {W}_{a}, {W}_{b} }, {a, b},...

24
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 01:27 2
Породите несколько слов, сформулируйте гипотезу. Прочитайте определение типов грамматик.
0
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 19:35  [ТС] 3
Я не понимаю етой штуки но сделать надо, поможете мне ? Я читал методичку не очень понял,, но сдать нужно до конца октября на ел почту преподу прислать. В любом случаи мне прийдется разобратся с етим, просто время поджимает
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 20:02 4
Нет, я не пишу полные решения. Возьмите S и начните его заменять согласно правилам. Например, S можно заменить на 0S три раза, получится 000S. Затем S можно заменить на A: 000A. Затем A можно заменить на A1 несколько раз. Наконец, A заменяется на пустое слово http://www.cyberforum.ru/cgi-bin/latex.cgi?\Lambda. Попробуйте разные последовательности замен и сформулируйте гипотезу о виде получающихся слов.
0
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 20:16  [ТС] 5
Если я чтото сформулирую напишите полное? Мне реально нужно сегодня ето отослать
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 20:19 6
Пишите ваши мысли, я поправлю.
0
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 21:07  [ТС] 7
Не успею я с етой фигней разобратся до 12.00 (((((((((((

Добавлено через 4 минуты
Вам спасибо за помощь, я реал не успею ето, я учил на втором курсе дискретную математику, но граматики вроде небыло

Добавлено через 9 минут
Помогите плз, я обещаю буду щяс ето розбирать мне прост оету фигню отправить надо до 12
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 21:09 8
Глубоко вздохните и начните следовать советам (по решению этой конкретной задаче) в сообщении №4. Сгенерируйте хотя бы 5 слов и напишите их.
0
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 21:39  [ТС] 9
S->000S
A->000A
A->000A1
A->A пустое както так?

Добавлено через 31 секунду
мне до 24.00 отослать надо, по украине

Добавлено через 22 секунды
там 5 задач надо решить за 2 часа

Добавлено через 2 минуты
000A1 -> A пустое
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 21:43 10
Возьмите букву S: это ваша начальная строчка. Начните заменять: выберите любое правило (у вас их 4) и замените в вашей строчке левую часть (слева от стрелки) на правую. Продолжайте с полученной строчкой до тех пор, пока строчка не перестанет содержать S или A, то есть будет состоять целиком из 0 и 1.

Например, из S за три замены правилом S -> 0S можно получить 000S. Дальше выбираете правило S -> A и заменяете, получается 000A. Затем выбираете правило A -> A1 и за две замены получаете 000A11. Наконец, заменяете A на пустую строчку, получается 00011 — это результат.

Попробуйте применять правила в другом порядке и количестве и напишите 5 строчек, состоящих из 0 и 1, которые получатся.
0
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 22:07  [ТС] 11
Результат ето не решение?
S->0000S,0000A,0000A1,000001

Добавлено через 51 секунду
Я не могу понять ка к в другой последовотельности, взять сначало S->А вы имете ввиду?

Добавлено через 2 минуты
количество то проблем нету поменять ето я могу
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 22:11 12
Цитата Сообщение от Anriuser Посмотреть сообщение
S->0000S,0000A,0000A1,000001
Да, это одна из возможных строк.

Цитата Сообщение от Anriuser Посмотреть сообщение
Я не могу понять ка к в другой последовотельности
Я же в сообщении №10 получил другую строку (не 000001).

Занумеруем правила:

1) S -> 0S
2) S -> A
3) A -> A1
4) A -> пустая строка.

Применяйте в таком порядке: 1, 1, 2, 3, 3, 3, 4.
Снова начните с S и применяйте в таком порядке: 1, 2, 3, 4.
Снова начните с S и применяйте в таком порядке: 1, 1, 2, 4.
Снова начните с S и применяйте в таком порядке: 2, 3, 3, 4.

Попробуйте еще один-два вывода и напишите все результаты (строки из 0 и 1). Сформулируйте гипотезу.
0
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 22:37  [ТС] 13
00S, 00A, 00A111, 001111
0S, 0A, 0A1, 011
00S,00A,001
A,A11,111

Добавлено через 44 секунды
Так?

Добавлено через 2 минуты
Мне еще 4 задания надо до 24.00 отправить надо, и еще оформить ето все
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 22:38 14
В последней замене в каждом случае вы заменяете A на 1, хотя правило 4) говорит заменять A на пустое слово (то есть просто стереть его). Поэтому в каждой строке должно быть на одну единицу меньше: 00111, 01, 00, 11. Раньше мы сгенерировали 000001 и 00011. У вас есть гипотеза, как можно описать эти строки (и остальные) в общем случае?
0
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 22:43  [ТС] 15
я хз ка кописать
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 22:46 16
Лучший ответ Сообщение было отмечено Anriuser как решение

Решение

Можно получить слово, состоящее из любого количества нулей (включая ноль нулей), за которым идет любое количество единиц. Такие слова можно обозначить http://www.cyberforum.ru/cgi-bin/latex.cgi?0^m1^n, где http://www.cyberforum.ru/cgi-bin/latex.cgi?m,n — неотрицательные целые числа.
1
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 22:49  [ТС] 17
я не понимаю
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 22:50 18
В сообщении №16 написан ответ: язык, порожденный грамматикой. Язык — это множество слов.
0
Anriuser
-1 / 1 / 1
Регистрация: 18.10.2013
Сообщений: 312
31.10.2016, 22:53  [ТС] 19
Так и написать ответ?

Добавлено через 20 секунд
у меня там еще 4 задачи, поможете?
0
3D Homer
Эксперт по математике/физике
1934 / 1306 / 444
Регистрация: 01.09.2014
Сообщений: 3,309
31.10.2016, 22:55 20
Можете написать: язык состоит из всех слов вида...

Добавлено через 19 секунд
Нет, у меня у самого дедлайн.
0
31.10.2016, 22:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2016, 22:55

Составить грамматику, порождающую формальный язык. Определить тип формальной грамматики и языка по классификации
Помогите, пожалуйста с данным заданием: 1. Составить грамматику, порождающую формальный язык;...

Определить тип грамматики по Хомскому
Помогите пожалуйста определить тип грамматики по Хомскому, правила которой имеют вид S -> аbSba ...

Описать язык грамматикой и автоматом
Дан КС-язык, описать его с помощью грамматики и автомата. Язык {ω € {a,b}+ | |ω|a≥|ω|b},где |ω|a и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru