ли этот контекст свободный или регулярный

Question

Строки над алфавитом {a, b, c, d} где нет c не сразу, за которым следует a и не d не сразу после b.

Это был бы контекст, свободный и не регулярный?

Answer 1

Чтобы ответить на такой вопрос, вы, как правило, захотите принять наиболее ограничительный вид языка, а затем попытайтесь опровергнуть его. Если вы не можете опровергнуть это, вам нужно найти способ выразить это, используя соответствующую грамматику или автомат. Если вы можете опровергнуть это, перейдите на следующий уровень иерархии и повторите.

В этом случае у вас есть как минимум два варианта, чтобы доказать, что язык не является регулярным: лемма перекачки для правильных языков и теорема Михилла-Нерода. Если язык не может быть доказан нерегулярно от них, вам нужно будет правильно выбрать правильную грамматику, регулярное выражение или конечный автомат для этого языка. Часто неудачные попытки использовать лемму о перекачке или теорему Михилла-Нерода дают некоторое представление о том, как вы можете найти такие представления регулярных языков (например, лемма накачки может показать вам, что должен существовать потенциал для цикла в конечный автомат, а теорема Михилла-Нерода может показать вам, сколько состояний должно иметь конечный автомат, и какие переходы должны проходить между ними).

Это был бы контекст, свободный и не регулярный?

Почему вы так говорите? Отправьте аргумент, ведущий к такому выводу, и я буду оценивать аргумент.