Во-первых, я бы исправил то, что вы сказали, чтобы уточнить, что мы говорим о неограниченных сравнениях. Мы можем иметь несколько сравнений, например, по модулю некоторого числа. Например, рассмотрим язык над {a, b, c, d}, где n (a) = n (b) = n (c) = n (d) (mod 5). У этого есть как минимум три сравнения, но язык все еще регулярен (оставлено как упражнение; подсказка: рассмотрите случаи n (a) = 0, 1, 2, 3, 4 отдельно).
Во-вторых, обратите внимание, что вы может иметь нерегулярные языки без (явных) сравнений длины. Например, рассмотрим контекстно-свободный язык палиндромов; есть палиндромы всех возможных длин.
В-третьих, мы должны уточнить, что проводимые сравнения должны носить конъюнктивный характер, а не дизъюнктивный. То есть, должно быть так, что все сравнения длин должны быть одновременно истинными, а не хотя бы одно из них истинными. Например, язык a ^ xb ^ yc ^ z с x = y или y = z не зависит от контекста. Аналогично, язык a ^ xb ^ yc ^ z, где не верно, что x = y = z, не зависит от контекста. Оба имеют несколько условий, но не удовлетворяют требованию, чтобы сравнение длины было одновременно истинным. (Примечание: не (x = y = z) <=> не (x = y и y = z) <=> x! = Y или y! = Z).
В-четвертых, это не так что контекстно-зависимые языки не могут делать больше двух сравнений длины. Вот не сокращающаяся грамматика (не сокращающиеся грамматики слабо эквивалентны CSG, подробности см. В Википедии) для ^ nb ^ nc ^ nd ^ 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
Вот вывод aaabbb ccc ddd:
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