CODEWITHSUNDEEP
context-free-grammarautomatafinite-automataturing-machinesautomata-theory
Piyush Sawarkar
Piyush Sawarkar

Reputation: 156

Can I classify a grammar on the basis of comparison of length

Whenever we have regular language then we can have no comparison.(for the obvious reason that it has no memory) And when context free language we can have Max 1 comparison. For example a^n b^n here length of a and b have just a single comparison... When comtext sensitive language we have Max 2 comparison and more than 2 comparison means unrestricted grammar. Are the above generalizations made by me any correct, if not please specify the issues..if I consider such statement.

Upvotes: 1

Views: 159

Answers (1)

Patrick87
Patrick87

Reputation: 28312

First, I'd amend what you've said to clarify that we're talking about unbounded comparisons. We can have multiple comparisons, e.g., modulo some number. For instance, consider the language over {a, b, c, d} where n(a) = n(b) = n(c) = n(d) (mod 5). This has at least three comparisons but the language is still regular (left as an exercise; hint: consider cases n(a) = 0, 1, 2, 3, 4 separately).

Second, note that you can have non-regular languages without (explicit) length comparisons. For instance, consider the context-free language of palindromes; there are palindromes of all conceivable lengths.

Third, we should clarify that the comparisons being made must be conjunctive in nature, rather than disjunctive. That is, it must be the case that all of the length comparisons must simultaneously be true, rather than at least one of them being true. For instance, the language a^x b^y c^z with x=y or y=z is context-free. Similarly, the language a^x b^y c^z where it is not true that x=y=z is context-free. These both have multiple conditions but do not satisfy the requirement that the length comparisons must simultaneously be true. (Note: not(x=y=z) <=> not(x=y and y=z) <=> x!=y or y!=z).

Fourth, it is not true that context-sensitive languages cannot do more than two length comparisons. Here's a non-contracting grammar (non-contracting grammars are weakly equivalent to CSGs, see Wikipedia for details) for 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

Here's a derivation of 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

Upvotes: 1

Related Questions