Помогите разобраться с грамматикой.

[voland]

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

Тоесть есь терминальный алфавит $\{1, 0\}$, нетерминальный алфавит , скажем, состоит из одного стартового символа $S$. Одно из правил $S\to 1$. И вот я что-то не соображу как задать правила порождающей грамматики, реализующее это "правило 110". Найдя такие правила, можно было бы сказать к какому классу она относиться (контекстно-свободная/несвободная/регулярная...)
Как бы не понятно как выразить эту "зависимость от соседей" в продукции....

Спасибо.

Андрей.

[_hum_]

voland в сообщении #589668 писал(а):

Я для примера хочу классифицировать грамматику, задаваемую правилом110

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

[voland]

Я хочу описать множество слов (язык) порождаемое правилом 110.

Тоесть этот язык порождается автоматом 110. Я хочу найти эквивалентное его определение через понятие грамматики. А потом найти место этой грамматики в иерархии Хомского.


Например, если взять фиксированный размер слова, скажем 4, то такой список правил порождал бы эквивалентный 110-му язык:

$S \to 0001$
$0001 \to 0011$
$0011 \to 0111$
$0111 \to 1101$

-- 27.06.2012, 19:39 --

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

[_hum_]

voland в сообщении #589823 писал(а):

Я хочу описать множество слов (язык) порождаемое правилом 110.

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

[мат-ламер]

Меня смущает, что павило 110 одномоментное, т.е. применяется ко всем символам из списка одновременно. Для грамматики бы лучше было, если правила применялись последовательно.