Создание грамматики из обычного языка

Question

У меня есть некоторые проблемы с определением грамматики для этого специального языка, надеюсь, вы могли бы помочь: Язык: Σ = {х, у, г} A = {w | w ∈ Σ ^ ∗ ∧ | w | _x mod 2> = | w | _y mod 2}

Поскольку это так сложно, я сначала попытался собрать все свойства в одну грамматику, поэтому | w | _x mod 2> = | w | _y mod 2 и w ∈ Σ ^ ∗, но без получения всех комбинаций, таких как cacbcacb и т.д.

Что я получаю, это что-то вроде: ccccc ... caa ... abcbbbcc и чем я пользуюсь ac -> ca и т. д., чтобы изменить комбинацию и получить каждое слово, которое я хочу.

Но можем ли мы сделать некоторую контекстно-свободную грамматику?

Мое решение

S → G | U | c | cS | ɛ
G → AGB | ɛ | cG
A → ɛ | a | cA
B → ɛ | bb | cB
U → ab | DaUbE | cU
D → a
E → b
ab → ba
ba → ab
ac → ca
ca → ac
bc → cb
cb → bc

Очень некрасиво.

Answer 1

Как вы говорите, этот язык является обычным, поэтому явно не требуется контекстно-зависимая грамматика.

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

Конвертировать конечный автомат в CFG почти тривиально. Каждое состояние становится нетерминальным, и вы можете читать произведения с переходов состояний. Если состояние P имеет переход к состоянию Q по символу a, CFG имеет продукцию Q -> P a. Стартовый символ затем имеет единицу продукции в каждом конечном состоянии И это все.