Несколько задач на определение языков грамматиками

Обозначения: конструкцией вида X^n обозначим повтор X n раз; конструкцией вида (XY...) обозначим группу XY..., понимаемую как единое целое (т.е. круглые скобки используем как метасимволы для группирования).

Задача1. Дан язык L1={ ab^nc}, n>0. Т.е. язык состоит из слов: abc, abbc, abbbc, ... . Составить формальную грамматику, описывающую этот язык.
Задача2. То же, что и в задаче1 для языка L2={ ab(bc)^na}, n>=0. (язык соcтоит из слов: aba, abbca, abbcbca, abbcbcbca. ...).
Задача3. То же, что и в задаче1 для языка L3={a(bc)^n(ca)^mab}; m,n>0.
Задача4. То же, что и в задаче1 для языка L4={ (01)^n23^n}; n>=0. Т.е. L4={2, 0123, 0101233, ...}
Задача5. То же, что и в задаче1 для языка L5={ a^nbbc^m, ca^k, dd}; m,n,k>0.

В предлагаемых решениях указывать номера задач. Допускаются различные варианты решений. Как обычно, оцениваю как результаты, так и активность.

2ПМ - обещанное

Вот пять пробных задач. Постарайтесь классифицировать по Хомскому как построенные Вами грамматики (надеюсь, такие будут), так и языки.

Зиновьев Александр аватар

Задача №1

Не уверен, что нужно оформлять решение так, но буду тогда первым набивать шишки.
Итак, первая задача у нас даже проще, чем приведенная в аудитории, поэтому грамматика должна быть построена следующим образом:

  1. S -> aZ;
  2. Z -> bZ;
  3. Z -> bZ1;
  4. Z1 -> с.

Т.к. описан самой простой автоматной грамматикой, то сам язык является А-языком.
Оформление дб таким?

ОК, Саша.

Всё правильно. Жаль только, что не вовремя. Предполагалось, это решить до сегодняшней лекции. Теперь задача выглядит тривиально. Впрочем, другие посложнее. Доброй ночи!

Малхожева Оксана аватар

Задача5. L5={ a^nbbc^m, ca^k, dd}; m,n,k>0.

  1. S->aS
  2. S->aS1
  3. S1->bS2
  4. S2->bS3
  5. S3->cS3
  6. S3->cS4
  7. S4->cS5
  8. S5->aS5
  9. S5->aS6
  10. S6->dS7
  11. S7->d

данный язык описан А-грамматикой,значит и сам язык является А-языком.

Задача 4

L4={ (01)^n23^n}; n>=0.

  1.  S->A2B
  2.  A->01A
  3.  A->01
  4.  B->3B
  5.  B->3

данный язык является КС-грамматикой

Оксана, нет.

Грамматика неверна. Язык должен включать слова трех типов.

Малхожева Оксана аватар

ошибка понятна

сейчас исправлю)

Малхожева Оксана аватар

Задача5. попытка №2)

  1. S->aS
  2. S->aS1
  3. S1->bS2
  4. S2->bS3
  5. S3->cS3
  6. S3->c
  7. S4->cS5
  8. S5->aS5
  9. S5->a
  10. S6->dS7
  11. S7->d

теперь вроде правильно..

Наташа, нет.

Даже не близко! Посмотрите внимательней на язык и примеры.

Оксана, нет2.

???

Малхожева Оксана аватар

да что такое...

я 3 слова описала..можно намек на ошибку?я какое то из слов неправильно описала?

Ваша грамматика

Элементарно. Ваша грамматика, Оксана, не порождает, например, слова dd.

Наташа,

В Вашей грамматике выводимо, например слово 01233333, заведомо языку не принадлежащее!

Малхожева Оксана аватар

ну как же...

из S6 следует это слово.Или из S должны выводиться все 3 слова?

Почитайте, что означает

Почитайте, что означает фраза: "язык, определяется грамматикой" и вообще какова точная связь грамматик и языков.

Малхожева Оксана аватар

множ-во слов

выведенных из ЦЕЛИ ГРАММАТИКИ..сейчас попробую переделать..

Малхожева Оксана аватар

ЗАДАЧА 5 ПОПЫТКА №1000000

  1. S->aQ
  2. S->cS5
  3. S->dS7
  4. Q->aS1
  5. S1->bS2
  6. S2->bS3
  7. S3->cS3
  8. S3->c
  9. S5->aS5
  10. S5->a
  11. S7->d

надеюсь теперь правильно условие поняла..

Оксана, НЕТ3

Оксана, НЕТ3

Малхожева Оксана аватар

попытка4

  1. S->aQ
  2. S->cS5
  3. S->dS7
  4. Q->aS1
  5. S1->bS2
  6. S2->bS3
  7. S3->cS4
  8. S4->cS4                                  
  9. S4->c
  10. S5->aS5
  11. S5->a
  12. S7->d

вот))

Иващенко Сергей аватар

Задача №2

  1. S->abZ;
  2. Z->a;
  3. Z->bcZ1;
  4. Z1->bcZ1;
  5. Z1->a;

Слова вроде выводятся правильно. А вот с определением типа грамматики и языка могу ошибиться...В связи с отсутствием на прошлой лекции...а информация на эту тему в интернете какая-то не понятная ... но я все таки предположу что данный язык описан А-грамматикой, значит и сам он является А-языком.

Малхожева Оксана аватар

нет

А-грамматикой он быть не может,т.к. в правиле если есть нетерминальный символ,то перед ним(после) всегда должен стоять ОДИН терминальный,у тебя же в S->abZ,например, перед нетерминальным Z стоят два терминальных a и b))

Иващенко Сергей аватар

ну я был уверен что

ну я был уверен что ошибся...надо лекцию будет восстановить!

Оксана, Сергей ...

Оксана:
попытка4 :(
коммент Сергею :)
Cергей: классификация(?)

Малхожева Оксана аватар

опять нет?...интересно..буду

опять нет?...интересно..буду дальше думать...

Оксана, да и остальные!

Оксана, да и остальные! Разберитесь повнимательней, из слов какого вида состоит язык. А уж потом описывайте его формально. Меня удручает тот факт, что ни только решить задачу, но даже просто найти ошибку в решении товарища 95% студентов группы не способны!
Ни одна из 5 задач (кроме тривиальной 1-й) полностью так и не решена. Пытались хоть что-то делать только четверо.

Зиновьев Александр аватар

5 задача

Добрался до сайта, попробую свой вариант 5ой предложить. У Оксаны увидел только, что буквы а и с в любом случае будут браться два раза, а они мб в слове и в единственном экземпляре.

  1. S->aS;
  2. S->aS1;
  3. S->cS4;
  4. S->dS5;
  5. S1->bS2;
  6. S2->bS3;
  7. S3->cS3;
  8. S3->c;
  9. S4->aS4;
  10. S4->a;
  11. S5->d.

Описан самой простой автоматной грамматикой, то сам язык является А-языком.

Зиновьев Александр аватар

2 задача

  1. S->aS1;
  2. S1->bS2;
  3. S2->a;
  4. S2->bS3;
  5. S3->cS2.

Описан самой простой автоматной грамматикой, то сам язык является А-языком.

Зиновьев Александр аватар

3 задача

  1. S->aS1;
  2. S1->bS2;
  3. S2->cS1;
  4. S1->cS2;
  5. S2->aS1;
  6. S1->aS3;
  7. S3->b.

Описан самой простой автоматной грамматикой, то сам язык является А-языком.

Зиновьев Александр аватар

4 задача

  1. S->2;
  2. S->0S1;
  3. S->2S2;
  4. S1->1S;
  5. S2->3S2;
  6. S2->3.

Описан самой простой автоматной грамматикой, то сам язык является А-языком.

Малхожева Оксана аватар

только подумала об этой ошибке..

не успела исправить,чтож надо было соображать мне быстрее и внимательнее решать и читать условия

Саша З.

Что-то правильно, что-то нет ...

Зиновьев Александр аватар

Вижу...

Четвертая неправильно решена точно.

Да и не только четвёртая...

Да и не только четвёртая...

Задача 3

L3={a(bc)^n(ca)^mab}; m,n>0

Решение Саши З. неверно, так как с помощью данной грамматики выводятся слова ( aab, abaab, abcab, acaab, и др.), не принадлежащие языку L3.
Попытаюсь исправить:

  1. S->aS1;
  2. S1->bS2;
  3. S2->cZ1;
  4. Z1->bS2;
  5. Z1->cS3;
  6. S3->aZ2;
  7. Z2->cS3;
  8. Z2->aS4;
  9. S4->b.

Задача 4

L4={ (01)^n23^n}; n>=0. Т.е. L4={2, 0123, 0101233, ...}
Попробую описать в КС-грамматике:

  1. S->2;
  2. S->ASB;
  3. A->0Z;
  4. Z->1;
  5. B->3.

Не знаю, можно ли так ...

Дмитрий М, Роман Н.

Да, Дмитрий, но вот классификации грамматик я не увидел.
Роман, задания касаются MS-DOS, они опубликованы ещё в 15.30 и Вы вольны, конечно, принять в них участие.

Классификация грамматик

В задаче 3 язык описан с помощью А-грамматики, значит язык L3 является A-языком.
В задаче 4 язык описан в КС-грамматике. Правильно?

Зиновьев Александр аватар

Мда

Подвело меня в 3й задаче желание сократить количество нетерминальных символов.

Я вот что-то не разберусь, в

Я вот что-то не разберусь, в задаче 4, разве будет степень одинаковой?

1ИС3, здравствуйте!

Зайдите в свою группу. Там мы и поработаем.

1ИС3, откликнитесь! И

1ИС3, откликнитесь! И перейдите в свою группу!