Context-Free Languages

The previous lesson established the measure that counts a language as regular: if the required state count does not grow as the universe grows, a fixed budget can be chosen for that language. Two examples passed this measure; “even a’s” wanted 2 states across all three universes, “ends with ab” wanted 3. Now a language that does not pass the measure is examined.

The language in question is: some number of a’s, followed by exactly the same number of b’s. This language demands a counting task; the number of a’s read must be held somewhere so the b’s can be counted against it. A finite automaton’s only memory is its state, and the state count is fixed. The whole weight of the question is here.

A Language That Requires Counting

The previous lesson’s three measures are used exactly as they were: the count of residual-language classes, the separated-prefix count, and the exhaustive count. All three run over the same universe, then the universe is swept. A second language is placed alongside: the balanced string, that is, a string where, counting a as an open and b as a close, no prefix ever has more closes than opens, and the two are equal at the end.

• MC10 — The target language equal_count: a string belongs to the language if its first half is all a’s, its second half is all b’s, and its length is even. The empty string belongs to the language.
• MC11 — The second target balanced is tested with a single counter: a increments it, b decrements it; the counter never drops below zero and is zero at the end.
• MC12 — The exhaustive count in this lesson runs from k=1 to 5. The number of five-state transition tables is $5^{10}$; this is the measure’s budget, and k=6 was not tried in this lesson.
• MC13 — The measurement never says “this language cannot be recognized” anywhere. The only thing it can say is what was found within the k values and length limits tried.

"""a^n b^n and the balanced language: class, separated prefix and exhaustive count
side by side."""
from itertools import product

ALPHABET = ("a", "b")


def strings(max_length):
    output = [""]
    for n in range(1, max_length + 1):
        output += ["".join(d) for d in product(ALPHABET, repeat=n)]
    return output


def equal_count(s):
    """Is it of the form a^n b^n."""
    n = len(s)
    if n % 2:
        return False
    half = n // 2
    return s[:half] == "a" * half and s[half:] == "b" * half


def balanced(s):
    """a opens, b closes; no prefix ever has more closes than opens."""
    counter = 0
    for c in s:
        counter += 1 if c == "a" else -1
        if counter < 0:
            return False
    return counter == 0


def distinguishability_classes(target, universe):
    """Distinguishability classes: the number of residual languages."""
    prefixes = {s[:i] for s in universe for i in range(len(s) + 1)}
    return len({frozenset(t for t in universe if p + t in target) for p in prefixes})


def separated_prefixes(target, universe):
    """Only a suffix whose BOTH extensions stay in the universe can separate two prefixes."""
    universe_set = set(universe)
    prefixes = sorted({s[:i] for s in universe for i in range(len(s) + 1)},
                       key=lambda p: (len(p), p))
    signature = {p: tuple((1 if p + t in target else 0) if p + t in universe_set else -1
                           for t in universe) for p in prefixes}
    selected = []
    for p in prefixes:
        if all(any(x >= 0 and y >= 0 and x != y
                   for x, y in zip(signature[p], signature[q])) for q in selected):
            selected.append(p)
    return len(selected)


def recognizer_exists(k, target, universe):
    """All k-state transition tables; the accepting set is chosen for consistency."""
    cells = [(state, symbol) for state in range(k) for symbol in ALPHABET]
    for targets in product(range(k), repeat=len(cells)):
        transitions = dict(zip(cells, targets))
        required, consistent = {}, True
        for s in universe:
            state = 0
            for symbol in s:
                state = transitions[(state, symbol)]
            wanted = s in target
            if required.setdefault(state, wanted) != wanted:
                consistent = False
                break
        if consistent:
            return True
    return False


print("length  strings   a^n b^n: class  prefix   balanced: class  prefix")
for length in (2, 4, 6, 8, 10):
    U = strings(length)
    h1 = frozenset(s for s in U if equal_count(s))
    h2 = frozenset(s for s in U if balanced(s))
    print(f"{length:6d}  {len(U):6d}  {distinguishability_classes(h1, U):15d}  {separated_prefixes(h1, U):5d}"
          f"  {distinguishability_classes(h2, U):15d}  {separated_prefixes(h2, U):5d}")
print()
print("exhaustive count: k = 1..5, ALL automata tried")
print("length  a^n b^n target                 smallest recognizing k")
for length in (2, 3, 4):
    U = strings(length)
    h = frozenset(s for s in U if equal_count(s))
    k = [i for i in (1, 2, 3, 4, 5) if recognizer_exists(i, h, U)]
    print(f"{length:6d}  {str(sorted(h)):28s}  {k[0] if k else 'none'}")

length  strings   a^n b^n: class  prefix   balanced: class  prefix
     2       7                4      3                4      3
     4      31                6      5                7      4
     6     127                8      7               11      5
     8     511               10      9               16      6
    10    2047               12     11               22      7

exhaustive count: k = 1..5, ALL automata tried
length  a^n b^n target                 smallest recognizing k
     2  ['', 'ab']                    3
     3  ['', 'ab']                    3
     4  ['', 'aabb', 'ab']            5

Three numbers side by side. Budget: state count 1 to 5, length limit 2 to 10. What the budget answers: the required state count grows as 3, 5, 7, 9, 11 for the a’s-then-b’s language, as 3, 4, 5, 6, 7 for the balanced language; at length 4 the exhaustive count finds the smallest k to be 5, matching the separated-prefix count exactly. What the budget fails to answer: that no fixed k suffices at any length. The measurement cannot say this; what it can say is that within the five lengths and five k values tried, the state count keeps growing without stopping.

The cause of the growth is in the language, not in the measurement. Consider first the prefixes made only of a’s: the two distinct prefixes a and aa are separated by the suffix b, because ab belongs to the language and aab does not; and both extensions are inside the universe. The same holds for aa and aaa with the suffix bb, and for aaa and aaaa with the suffix bbb. In a universe with length limit 2m, this chain stretches to m+1 prefixes, and every prefix in the chain demands a separate state. The chain gets longer as the limit grows. The statement here, precisely, is: for every fixed k, a length was measured at which that k does not suffice; the statement “it never suffices” is the theory’s result and is not established by a run.

The first two rows of the exhaustive-count table should also be read. In the length-2 and length-3 universes, the target stays the same, because no odd-length string belongs to the language; the smallest k is 3 in both. At length 4, the moment aabb enters the target, the count jumps to 5. That is, the required state count rises not with the number of strings added to the universe, but with a new counting depth being added to the language. The two-state automaton’s memory ran out at one bit; what is required here is a counter that holds how many a’s were read, and the number of values the counter can take rises with the length.

The one-off difference between the class column and the prefix column shows that the previous lesson’s over-count continues: for the a’s-then-b’s language, the class is 4, 6, 8, 10, 12 while the separated prefix is 3, 5, 7, 9, 11. The two columns have the same slope; both grow linearly. For the balanced language, though, the two columns diverge — the class rises to 22 while the prefix stays at 7 — the gap between the cheap measure and the tested measure varies by language, and this is why the cheap measure is never written on its own.

A Production Rule Does What the Automaton Cannot

Growing the budget is one path. The second path is changing the model. A production rule is a rule that permits replacing a symbol with a string; applying rules one after another is called derivation. A language whose every string can be derived from a finite set of rules is called a context-free language.

Grammar and parsing were established in the Compilation Stages lesson of the How Computers Work course; tokens, the abstract syntax tree, and the embedding of operator precedence into the tree were explained there and are not repeated here. The only thing this lesson adds is the measure: whether the set a rule generates is exactly identical to the target language.

• MC14 — The rule S -> a S b | empty carries two options and is a single line. Derivation depth is how many times the rule is applied.
• MC15 — The second rule S -> a S b S | empty generates balanced strings. The measurement is whether the generated set equals the set of balanced strings in the universe; a subset is not enough.
• MC16 — The rule’s description and run are measured separately: the description is the line count, the run is the derivation depth.

"""Production rule: the description stays constant, the derivation depth grows
with the input."""
from itertools import product

ALPHABET = ("a", "b")
RULE = {"S": [("a", "S", "b"), ()]}          # S -> a S b | empty


def strings(max_length):
    output = [""]
    for n in range(1, max_length + 1):
        output += ["".join(d) for d in product(ALPHABET, repeat=n)]
    return output


def equal_count(s):
    n = len(s)
    if n % 2:
        return False
    half = n // 2
    return s[:half] == "a" * half and s[half:] == "b" * half


def balanced(s):
    counter = 0
    for c in s:
        counter += 1 if c == "a" else -1
        if counter < 0:
            return False
    return counter == 0


def derive(max_depth):
    """Strings generated by the rule in at most `max_depth` steps."""
    generated = {""}
    previous = {""}
    for _ in range(max_depth):
        new_set = {"a" + s + "b" for s in previous}
        generated |= new_set
        previous = new_set
    return generated


def derive_balanced(max_length):
    """S -> a S b S | empty; all derivations not exceeding max_length."""
    set_, changed = {""}, True
    while changed:
        changed = False
        for x in list(set_):
            for y in list(set_):
                new_string = "a" + x + "b" + y
                if len(new_string) <= max_length and new_string not in set_:
                    set_.add(new_string)
                    changed = True
    return set_


print("S -> a S b | empty")
print("depth  generated  longest  covers same-length target")
for d in (1, 2, 3, 4, 5):
    U = derive(d)
    target = {s for s in strings(2 * d) if equal_count(s)}
    print(f"{d:5d}  {len(U):9d}  {max(len(s) for s in U):7d}  {target <= U}")
print("  generated at depth 3:", sorted(derive(3)))
print()
print("S -> a S b S | empty")
print("length  generated  balanced strings  same set")
for length in (2, 4, 6, 8):
    T = derive_balanced(length)
    D = {s for s in strings(length) if balanced(s)}
    print(f"{length:6d}  {len(T):9d}  {len(D):16d}  {T == D}")

S -> a S b | empty
depth  generated  longest  covers same-length target
    1          2        2  True
    2          3        4  True
    3          4        6  True
    4          5        8  True
    5          6       10  True
  generated at depth 3: ['', 'aaabbb', 'aabb', 'ab']

S -> a S b S | empty
length  generated  balanced strings  same set
     2          2                 2  True
     4          4                 4  True
     6          9                 9  True
     8         23                23  True

The one-line rule generates "", ab, aabb, aaabbb in three derivation steps; this is the entirety of the a’s-then-b’s strings in the universe of length at most 6. The same result continues up to length 10 at five levels of depth: the coverage column reads True in all five rows. For the second rule the measure is stricter, because what is tested is not a subset but equality: the 23 strings generated up to length 8 are exactly the 23 balanced strings in the universe.

This is the opposite of what the previous section measured. For the same language, while the automaton’s required state count rose from 3 to 11, the rule’s line count stayed at 1. Changing the model class is a different thing entirely from growing the budget: the former keeps the description’s size fixed, the latter grows the description.

Where the Budget Goes

The cost the two models pay does not sit in the same place. The table below places the two sections’ numbers side by side; the state column comes from the separated-prefix count, the depth column from the derivation measurement.

Length limit	Automaton: states required	Rule: lines	Rule: derivation depth
2	3	1	1
4	5	1	2
6	7	1	3
8	9	1	4
10	11	1	5

What grows in the automaton is the description: a bigger machine has to be written for longer strings, and the machine itself grows along with the input. What grows in the rule is the run: the rule stays the same, it is only applied more times. When measuring a model’s power, the question to ask should not be “how many steps does it spend,” but “what grows along with the input.”

This distinction has a cost too, and it is not hidden. A rule does not decide whether a string belongs to the language with a finite automaton’s single pass; it has to search for the derivation, and searching is more expensive than a single pass. The measurement shows this too: generating the 23 strings for the balanced language up to length 8 required continuing the iteration until the set settled at a fixed point. Power does not come for free; what is paid, in place of description size, is search.

Summary

• For the language requiring an equal count of a’s and b’s, the required state count grows with the length limit as 3, 5, 7, 9, 11; for the balanced language, as 3, 4, 5, 6, 7.
• In the length-4 universe, all automata from k=1 to 5 were tried, and the smallest k came out to 5; this number is exactly the same as the separated-prefix measure.
• That no fixed k suffices at any length was not measured and cannot be measured; what is measured is that, for every k tried, a length was found at which that k does not suffice.
• The one-line rule S -> a S b | empty generates every target string of length at most 6 in three derivation steps; S -> a S b S | empty generates all 23 balanced strings up to length 8, and nothing extra.
• What grows with the input is the description in an automaton, the run in a production rule; changing the model class is a different thing from growing the budget.
• The cost of the power was measured too: the rule does not decide in a single pass, it searches for the derivation; description size is gained, search is paid.

Next Step

Both models were defined with a limit: one by state count, the other by rule form. The next lesson loosens the limit as much as possible and builds a model with a tape that can overwrite the symbol it reads and move back and forth. The question to be asked is: can we count all the members of this model one by one, and once counted, can we learn how many of them halt with a step budget. The first half of the answer is easier than expected, the second half is harder than expected.