Форум программистов, компьютерный форум, киберфорум
Наши страницы
Теория автоматов
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
GOLD950
1 / 1 / 0
Регистрация: 16.02.2016
Сообщений: 42
1

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

01.10.2018, 18:47. Просмотров 542. Ответов 13
Метки нет (Все метки)

1. L(G)={(ac)n| n>0, a∈{b, d}, c∈{+, -}}
-составить грамматику, порождающую формальный язык
-определить тип формальной грамматикии языка по классификации Хомского


2. В строке должна встретиться хотя бы одна буква а : bbbbbabbb aaaaaaaaaaa
-составить грамматику.

Помогите, пожалуйста! Буду очень признателен
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2018, 18:47
Ответы с готовыми решениями:

Построить грамматику, порождающую формальный язык
L(G) = {(ab)^n (cb)^m | n, m>=0} 1) Построить грамматику, порождающую формальный язык. 2)...

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

Составить грамматику, порождающую формальный язык
1. Составить грамматику, порождающую формальный язык: L(G)={a1a2...ana1a2...an | ai Є {c, d}};

Составить грамматику, порождающую формальный язык
L(G)={a1a2…anan…a2a1 | ai∈{0, 1}} Кто в этом шарит,помогите решением или дельным советом)...

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

13
3D Homer
Эксперт по математике/физике
2178 / 1483 / 497
Регистрация: 01.09.2014
Сообщений: 3,769
01.10.2018, 21:41 2
Цитата Сообщение от GOLD950 Посмотреть сообщение
1. L(G)={(ac)n| n>0, a∈{b, d}, c∈{+, -}}
Что такое (ac)n?

Составьте для начала грамматику, порождающую {a^n | n > 0}.

Цитата Сообщение от GOLD950 Посмотреть сообщение
2. В строке должна встретиться хотя бы одна буква а : bbbbbabbb aaaaaaaaaaa
Составьте для начала грамматику, порождающую любы слова в алфавите {a, b},
0
GOLD950
1 / 1 / 0
Регистрация: 16.02.2016
Сообщений: 42
04.10.2018, 14:36  [ТС] 3
Извиняюсь, (ac)^n.

Грамматика для {a^n | n > 0}
S -> Aa | a
A -> a
Так?

Грамматика для bbbbbabbb aaaaaaaaaaa
S -> a | b | aA | aB | bA | bB
A -> a
B -> b
Правильно?
0
3D Homer
Эксперт по математике/физике
2178 / 1483 / 497
Регистрация: 01.09.2014
Сообщений: 3,769
04.10.2018, 15:21 4
Цитата Сообщение от GOLD950 Посмотреть сообщение
Грамматика для {a^n | n > 0}
S -> Aa | a
A -> a
Так?
Нет. Попробуйте вывести в вашей грамматике слово aaa.

Цитата Сообщение от GOLD950 Посмотреть сообщение
Грамматика для bbbbbabbb aaaaaaaaaaa
S -> a | b | aA | aB | bA | bB
A -> a
B -> b
Правильно?
То же замечание. Если у вас нет рекурсии (когда нетерминал порождает, возможно, через несколько шагов, строчку с самим собой), то все порожденные слова будут короче некоторой константы. И я просил написать грамматику не для bbbbbabbb aaaaaaaaaaa, а для любых слов в алфавите {a, b}.
0
04.10.2018, 15:21
GOLD950
1 / 1 / 0
Регистрация: 16.02.2016
Сообщений: 42
04.10.2018, 16:11  [ТС] 5
1. S -> Aa | a
A -> Aa | a
S -> Aa -> Aaa -> aaa

2. S -> a | b | aA | aB | bA | bB
A -> a | aA | aB
B -> b | bA | bB

Вот так?
0
Бард
153 / 102 / 58
Регистрация: 12.07.2018
Сообщений: 258
04.10.2018, 16:28 6
Цитата Сообщение от GOLD950 Посмотреть сообщение
1. S -> Aa | a
A -> Aa | a
S -> Aa -> Aaa -> aaa
Можно проще:
S->Sa|a

Добавлено через 3 минуты
Для второй грамматики также достаточно одного нетерминала.
0
GOLD950
1 / 1 / 0
Регистрация: 16.02.2016
Сообщений: 42
04.10.2018, 16:33  [ТС] 7
Можешь еще подсказать, грамматика порождающая данный язык L(G)={(ac)n| n>0, a∈{b, d}, c∈{+, -}}, такого вида?:
S -> Fb+ | Fb- | Fd+ | Fd-
F -> b+ | b- | d+ | d-
0
Бард
153 / 102 / 58
Регистрация: 12.07.2018
Сообщений: 258
04.10.2018, 16:50 8
Цитата Сообщение от GOLD950 Посмотреть сообщение
такого вида?:
Нет, длинные цепочки не выводятся.
0
3D Homer
Эксперт по математике/физике
2178 / 1483 / 497
Регистрация: 01.09.2014
Сообщений: 3,769
04.10.2018, 20:38 9
Цитата Сообщение от GOLD950 Посмотреть сообщение
Можешь еще подсказать, грамматика порождающая данный язык L(G)={(ac)n| n>0, a∈{b, d}, c∈{+, -}}
Пользуясь подсказкой Бард, сначала напишите грамматику, порождающую строки F^n для любого n > 0, где F — нетерминал. Затем добавьте F -> AC, а из A и C уже получите то, о чем говорится в условии.

Вообще вам следовало посмотреть десяток примеров грамматик в учебнике, чтобы появилась какая-то интуиция. Правила S -> Sa | a — это не супер сложно.
0
GOLD950
1 / 1 / 0
Регистрация: 16.02.2016
Сообщений: 42
04.10.2018, 20:41  [ТС] 10
Так?
S -> Fb+ | Fb- | Fd+ | Fd- | b+ | b- | d+ | d-
F -> Fb+ | Fb- | Fd+ | Fd- | b+ | b- | d+ | d-
0
3D Homer
Эксперт по математике/физике
2178 / 1483 / 497
Регистрация: 01.09.2014
Сообщений: 3,769
04.10.2018, 20:47 11
Так тоже можно. Лучше убрать вторую строчку, а в первой заменить F на S. Но вы не воспользовались моим предложением.
0
GOLD950
1 / 1 / 0
Регистрация: 16.02.2016
Сообщений: 42
10.10.2018, 14:18  [ТС] 12
Может кому пригодится:
1. L(G)={(ac)^n | n>0, a∈{b, d}, c∈{+, -}}
S -> acF | ac
F -> acS
a -> b | d
c -> +| -
Тип 2. Контекстно свободная грамматика

2. В строке должна встретиться хотя бы одна буква а : bbbbbabbb aaaaaaaaaaa
-составить грамматику.
S -> a | F
F -> aS | bS
0
Sindbad_M
128 / 127 / 37
Регистрация: 23.05.2016
Сообщений: 520
10.10.2018, 16:21 13
Цитата Сообщение от GOLD950 Посмотреть сообщение
S -> a | F
F -> aS | bS
разве строка
Цитата Сообщение от GOLD950 Посмотреть сообщение
bbbbbabbb
выводима из этой грамматики?
0
3D Homer
Эксперт по математике/физике
2178 / 1483 / 497
Регистрация: 01.09.2014
Сообщений: 3,769
10.10.2018, 17:46 14
Цитата Сообщение от GOLD950 Посмотреть сообщение
1. L(G)={(ac)^n | n>0, a∈{b, d}, c∈{+, -}}
S -> acF | ac
F -> acS
a -> b | d
c -> +| -
Первые две строчки не выводят acac. Лучше так: S -> acS | ac.
0
10.10.2018, 17:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.10.2018, 17:46

Составить грамматику, порождающую формальный язык
Может, у кого есть решение? 1) составить грамматику, порождающую формальный язык, заданный в...

Составить грамматику, порождающую формальный язык
1. Составить грамматику, порождающую формальный язык: L(G)={wcwcw | wЄ{a, b}^+}; 2. Определить тип...

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


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

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

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