Могу ли я классифицировать грамматику на основе сравнения длины

Всякий раз, когда у нас есть обычный язык, у нас не может быть сравнения (по очевидной причине, что у него нет памяти). А когда у нас контекстно-свободный язык, у нас может быть сравнение Max 1. Например, a ^ n b ^ n здесь длина a и b имеет только одно сравнение ... Когда язык, чувствительный к контексту, у нас есть сравнение Max 2, а сравнение более 2 означает неограниченную грамматику. Являются ли приведенные выше обобщения правильными, если нет, укажите вопросы, если я считаю такое утверждение.


turing-machines finite-automata context-free-grammar automata automata-theory
person Piyush Sawarkar    schedule 13.02.2020    source источник
comment
Не совсем правильно. Рассмотрим CFG S->AZ; A->aAb|ab; Z->yZz|yz. Это соответствует языку с двумя сравнениями: количество a = количеству b и количество y = количеству z. Следуя этому шаблону, вы можете определить CFG с произвольным количеством сравнений. Вы правы в том, что они довольно ограничены в видах сравнений, которые они могут выражать.   -  person Welbog    schedule 13.02.2020

Ответы (1)


arrow_upward
1
arrow_downward

Во-первых, я бы изменил то, что вы сказали, чтобы уточнить, что мы говорим о неограниченных сравнениях. У нас может быть несколько сравнений, например, по модулю некоторого числа. Например, рассмотрим язык над {a, b, c, d}, где n(a) = n(b) = n(c) = n(d) (mod 5). Здесь есть как минимум три сравнения, но язык по-прежнему регулярен (оставлено в качестве упражнения; подсказка: рассмотрим случаи n(a) = 0, 1, 2, 3, 4 отдельно).

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

В-третьих, мы должны уточнить, что проводимые сравнения должны носить конъюнктивный, а не дизъюнктивный характер. То есть должно быть так, что все сравнения длин должны быть истинными одновременно, а не хотя бы одно из них. Например, язык a^x b^y c^z с x=y или y=z не имеет контекста. Точно так же язык a ^ x b ^ y c ^ z, где неверно, что x = y = z, является контекстно-свободным. Оба они имеют несколько условий, но не удовлетворяют требованию, чтобы сравнения длин одновременно были истинными. (Примечание: не(x=y=z) ‹=> не(x=y и y=z) ‹=> x!=y или y!=z).

В-четвертых, неверно, что контекстно-зависимые языки не могут выполнять более двух сравнений длины. Вот неконтрактная грамматика (неконтрактные грамматики слабо эквивалентны CSG, подробности см. в Википедии) для a^n b^n c^n d^n:

S -> BCDT
T -> ABCDT | W
BA -> AB
CA -> AC
CB -> BC
DA -> AD
DB -> BD
DC -> CD
DW -> Wd
CW -> Xc
CX -> Xc
BX -> Yb
BY -> Yb
AX -> Za
AZ -> Za
Z -> e

Вот вывод aaabbbcccddd:

S
BCDT
BCDABCDT
BCDABCDABCDT
BCDABCDABCDW
BCADBCDABCDW
BACDBCDABCDW
ABCDBCDABCDW
ABCBDCDABCDW
ABBCDCDABCDW
ABBCCDDABCDW
ABBCCDADBCDW
ABBCCADDBCDW
ABBCACDDBCDW
ABBACCDDBCDW
ABABCCDDBCDW
AABBCCDDBCDW
AABBCCDBDCDW
AABBCCBDDCDW
AABBCBCDDCDW
AABBBCCDDCDW
AABBBCCDCDDW
AABBBCCCDDDW
AABBBCCCDDWd
AABBBCCCDWdd
AABBBCCCWddd
AABBBCCXcddd
AABBBCXccddd
AABBBXcccddd
AABBYbcccddd
AABYbbcccddd
AAYbbbcccddd
AZabbbcccddd
Zaabbbcccddd
aaabbbcccddd
person Patrick87    schedule 13.02.2020