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

Обозначения: конструкцией вида 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, откликнитесь! И перейдите в свою группу!