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

[Whiteboss]

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

[iifat]

Что-то не похоже это, имхо, на КС-язык.

[NikolayPrimachenko]

Интересное задание. Пока не подошли разбирающиеся в этом люди, рискну предположить, что для решения необходимо наложить на возможные в языке слова гораздо более сильные ограничения, потому что при указанных ограничениях в общем случае язык будет, как мне кажется, контекстно-зависимым. Например, для КС-языка, в котором возможны только слова "0001", "00010001", "000100010001", ..., легко построить грамматику. И в то же время выполнены оба условия задачи: нулей на три больше, чем единиц, и слово не заканчивается на "111". Тупое, конечно, формальное решение, но решение.

[iifat]

Похоже, я был неправ. Попробуйте взять задачу попроще (например, отсюда, последнюю, с языком $0^n1^n$) и постепенно довести до вашего случая. Потом по автомату построть грамматику.

[arseniiv]

NikolayPrimachenko в сообщении #1309904 писал(а):

Тупое, конечно, формальное решение, но решение.

Это не формальное решение, потому что язык дан какой дан, его нельзя сужать.

-- Пт май 04, 2018 17:28:17 --

Кстати, кажется, такие задачи бывают особо трудными, когда пытаешься написать в некотором смысле минимальную грамматику (в худшем случае однозначную). Этого, понятное дело, не нужно пытаться — вопрос об однозначности встаёт обычно для более «осмысленных» языков (типа современных языков программирования), и там эта задача нередко бывает тривиальной, чем для произвольного языка (притом есть КС-языки, не допускающие однозначной грамматики, так что иногда это вообще невозможно).

[NikolayPrimachenko]

(Оффтоп)

arseniiv,
Если я правильно понял небрежную запись, в задаче только три явно сформулированных условия:

1. Слова из нулей и единиц.
2. Количество нулей в словах на три больше, чем единиц. (Выше у меня очевидная ошибка --- выполняется другое условие: "в три раза больше". Надо было так: "10000", "1010000", "101010000"...),
3. Слова не заканчиваются на "111".

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

Это пояснение к фразе "тупое формальное решение". Я уверен, что употребил в ней первые два слова более-менее правильно.

Что касается настоящего решения, соответствующего истинному содержанию задачи (со всеми не высказанными явно предположениями), то я жду ТС-а. Если он или она долго не появится, надеюсь, что Вы и/или iifat разъясните "для тупых" или, еще лучше, дадите полное решение. (Ведь эта задача не относится к простым учебным?) Сам решить не смог. Жду халявы.

[mihaild]

Как построить грамматику для языка, слова которого содержат на три нуля больше чем единиц, и заканчиваются скажем на 010, понятно? (это в точности конкатенация языка, слова которого содержат на два нуля больше, чем единиц, и однословного языка)
Ну а дальше объединение аналогичных 7 языков.

[arseniiv]

(Оффтоп)

NikolayPrimachenko в сообщении #1310254 писал(а):

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

Вы так говорите, как будто «всех» в подобных описаниях не опускается почти всюду. Кроме того, оно даже могло быть в оригинале, а ТС просто его забыл. С таким «формальным» решением наверняка пошлют (переделывать). Формальным можно было бы назвать решение, пускающееся в детали больше надобности или проходящее в выкладках для общего случая мимо какой-нибудь упростившей бы всё идеи (скажем, решать простые геометрические задачи аналитически и притом в координатах).

NikolayPrimachenko в сообщении #1310254 писал(а):

Ведь эта задача не относится к простым учебным?

Ну как сказать. Вот mihaild всю идею описал.

[NikolayPrimachenko]

mihaild, спасибо Вам! Да, понятно. Главное, что теперь ясно, какой поворот мысли оказался для меня трудным. Несложный поворот, но...

arseniiv, Вам тоже спасибо!

(Оффтоп)

Однако : "Формальный ... 4. Не считающийся с существом дела, проникнутый формализмом." Существо дела -- это, в нашем случае, смысл задачи с учетом опущений. А не считающийся с существом -- это без учета недосказанного, строго по букве.

[iifat]

(Оффтоп)

NikolayPrimachenko в сообщении #1310284 писал(а):

Однако

Таки ж простите, но ваша позиция несколько напоминает анекдот (сходу нашёл не самый короткий вариант, ну да ладно). И ведь действительно — не придерёшься.