Star-free languages and the full picture

We’ve now seen a local branch (SL $\subset$ LT), a piecewise branch (SP $\subset$ PT), and TSL crosscutting both. What class contains these branches but still excludes some regular languages? The answer is the star-free languages.

Star-free languages

A language is star-free if it can be described by a generalized regular expression that uses union, concatenation, and complement but not Kleene star (McNaughton and Papert 1971; Schützenberger 1965). That is, we replace the $*$ operation with $\overline{\cdot}$ (complement with respect to $\Sigma^*$).

Why is every star-free language regular? Use structural induction on a star-free expression. Start with the atomic languages $\emptyset$, $\{\epsilon\}$, and $\{a\}$ for $a\in\Sigma$, all of which are regular. Now suppose the immediate subexpressions describe regular languages. Their union and concatenation are regular by the constructions from the preceding sections, and the complement of either one is regular after determinization and completion. Each licensed star-free constructor thus preserves regularity. Since every star-free expression has a finite construction, its language is regular.

This change carves out a particular subclass of the regular languages. In the presence of complement, removing Kleene star rules out the cyclic behavior needed for modular counting. For instance, the language $\{w \in \{a, b\}^* \mid |w|_a \equiv 0 \pmod{2}\}$—strings with an even number of $a$’s—is regular (you can build a two-state DFA for it) but not star-free. This does not mean that every regular expression containing a star performs modular counting; it means that some regular languages requiring modular counting have no star-free description.

We can build star-free expressions using arcweight by constructing automata with union, concat, and difference (complement) only.

Build a star-free language using only union, concatenation, and complement

import arcweight

# Alphabet: {a, b}
syms = arcweight.SymbolTable()
syms.add_symbol('<eps>')
a = syms.add_symbol('a')
b = syms.add_symbol('b')

# Sigma-star: accepts all strings over {a, b}
sigma_star = arcweight.VectorFst()
s = sigma_star.add_state()
sigma_star.set_start(s)
sigma_star.set_final(s, 0.0)
sigma_star.add_arc(s, a, a, 0.0, s)
sigma_star.add_arc(s, b, b, 0.0, s)

# Single-symbol FSAs
fst_a = arcweight.VectorFst()
s0 = fst_a.add_state()
s1 = fst_a.add_state()
fst_a.set_start(s0)
fst_a.set_final(s1, 0.0)
fst_a.add_arc(s0, a, a, 0.0, s1)

fst_b = arcweight.VectorFst()
s0 = fst_b.add_state()
s1 = fst_b.add_state()
fst_b.set_start(s0)
fst_b.set_final(s1, 0.0)
fst_b.add_arc(s0, b, b, 0.0, s1)

# A star-free description may use Σ* because Σ* = complement(∅).
# We construct the empty-language acceptor first to make that identity explicit.
empty = arcweight.VectorFst()
s = empty.add_state()
empty.set_start(s)
# No final state: this machine accepts nothing.

# `arcweight.difference` requires an explicit machine for the ambient universe,
# so the executable code uses `sigma_star` above to compute complements.

# "Strings that contain [ab] as a substring" (star-free):
# Σ* ∘ {a} ∘ {b} ∘ Σ* — but this uses concatenation, not star.
# We concatenate with sigma_star (= complement(∅)) on both sides.
ab_substr = arcweight.concat(
    arcweight.concat(sigma_star, fst_a),
    arcweight.concat(fst_b, sigma_star),
)

# "Strings that do NOT contain [ab]" (complement of the above)
no_ab = arcweight.difference(sigma_star, ab_substr)
no_ab = arcweight.minimize(no_ab)

print(f"no_ab states: {no_ab.num_states()}")

The McNaughton-Papert theorem

McNaughton and Papert (1971) and Schützenberger (1965) give an algebraic characterization of the star-free languages: a regular language is star-free if and only if its syntactic monoid is aperiodic, meaning it contains no nontrivial cyclic groups. The equivalent minimal-automaton statement is that a regular language is star-free if and only if its minimal DFA is counter-free: there is no state $q$, nonempty string $w$, and integer $n > 1$ such that $\delta(q,w^n)=q$ but $\delta(q,w)\neq q$. In other words, if iterating some string $w$ cycles a state back to itself, then one application of $w$ must already return to that state.

There is also a logical characterization: the star-free languages are exactly the languages definable in first-order logic with the linear order and successor predicates on string positions. This connects the subregular hierarchy to a broader program of relating language classes to logical expressiveness.

We won’t prove these equivalences here. For current purposes, their upshot is that the regular languages outside the star-free class require modular counting, while no known phonological pattern requires counting modulo a number.

The complete hierarchy

We can now assemble the full picture. The following containments are all proper:

\[\text{SL}_k \subset \text{SL}_{k+1} \subset \ldots \subset \text{SL} \subset \text{LT} \subset \text{Star-Free} \subset \text{Regular}\] \[\text{SP}_k \subset \text{SP}_{k+1} \subset \ldots \subset \text{SP} \subset \text{PT} \subset \text{Star-Free} \subset \text{Regular}\]

where SL $= \bigcup_k \text{SL}_k$ and SP $= \bigcup_k \text{SP}_k$. TSL sits on a third branch: it properly contains SL, is properly contained in the star-free languages, and is incomparable with LT and PT (Heinz et al. 2011). Thus, the relationships among the branches are not captured by a single linear ordering.

Question

The language “strings over $\{a, b\}$ with an even number of $a$’s” is regular. Is it star-free?

Answer

No. This language requires counting $a$’s modulo 2, which requires a cyclic group in the syntactic monoid. The minimal DFA has two states that cycle with each $a$, making it a counter. Since the syntactic monoid is not aperiodic, the language is not star-free.

We can spell out the counter-free argument without computing the full syntactic monoid. A two-state DFA recognizes the language: let $q_{\mathrm{even}}$ be the initial and final state and $q_{\mathrm{odd}}$ the other state; a swaps them and b leaves them unchanged.

This DFA is minimal. Both states are reachable, by $\epsilon$ and a, respectively. They are also distinguishable by the empty suffix: stopping in $q_{\mathrm{even}}$ accepts, while stopping in $q_{\mathrm{odd}}$ rejects. Thus, no equivalent DFA can merge them. And every string reaches one of the two states according to the parity of its number of as, so the two states exhaust the equivalence classes.

Now read one and then two copies of a from the even state:

\[ \delta(q_{\mathrm{even}},a)=q_{\mathrm{odd}} \quad\text{but}\quad \delta(q_{\mathrm{even}},a^2)=q_{\mathrm{even}}. \]

Thus, the nonempty string $a$ forms a cycle of length $2$: applying it twice returns the state, while applying it once does not. The minimal DFA violates the counter-free condition, so the McNaughton-Papert theorem rules out any star-free description.

The empirical picture

Across the work cited here, attested phonological patterns tend to fall into the lower levels of this hierarchy (Heinz 2018; Rogers et al. 2013; Lambert et al. 2021; Graf 2017).

Most phonotactic constraints (restrictions on what sequences of sounds can appear) are SL—they depend on short contiguous contexts.
Long-distance phonological processes like harmony are typically SP or TSL.
Very few phonological patterns require even LT or PT.
No known phonological pattern requires the full power of the regular languages.

There is nothing in the definition of a DFA that prevents a phonological pattern from using modular counting or other non-star-free capabilities. That phonological patterns don’t use them is an empirical observation about natural language, not a logical necessity.

Learnability revisited

One candidate explanation for why phonological patterns cluster in the subregular hierarchy comes from learnability. Recall Gold’s result: over a fixed nonempty finite alphabet $\Sigma$, if a hypothesis class contains every finite subset of $\Sigma^*$ and at least one infinite language, no learner can identify every member of that class in the limit from arbitrary positive text (Gold 1967). The regular languages meet this condition. If particular restricted subregular families are identifiable from positive data, their learnability may help explain why phonological patterns cluster there.

The scope of the positive results matters. Heinz (2010) describes the simple factor learner for SL-$k$ when $k$ is known in advance and proves positive-data identification for precedence languages, which correspond to SP-$2$ (see also Rogers et al. 2010). The constructions below likewise hold a finite alphabet and $k$ fixed. They do not establish that every unbounded union—or every class in the hierarchy—is identifiable from positive data.

Learning SL languages

Recall from the section on SL languages that an SL-$k$ language is determined by a set of forbidden $k$-grams $\mathcal{F}$: a string is in the language if and only if none of its $k$-grams (in the boundary-augmented string) appear in $\mathcal{F}$. The learning algorithm exploits this directly.

Given a parameter $k$ and a stream of positive examples $w_1, w_2, \ldots$ from an unknown SL-$k$ language $L$:

Initialize $\mathcal{A} = \emptyset$ (the set of attested $k$-grams).
For each new example $w_i$, extract all $k$-grams from the augmented string $\rtimes^{k-1} w_i \ltimes^{k-1}$ and add them to $\mathcal{A}$.
At any point, the learner’s current hypothesis is the SL-$k$ language with forbidden factors $\mathcal{F} = (\Sigma \cup \{\rtimes, \ltimes\})^k \setminus \mathcal{A}$—that is, every $k$-gram that has not yet been observed is assumed forbidden.

The learner starts maximally restrictive (everything is forbidden) and relaxes constraints as it sees evidence. Since the alphabet is finite, there are only finitely many possible $k$-grams. After enough examples, every $k$-gram that is licit in $L$ will have been observed at least once, and the learner’s hypothesis will stabilize at $L$.¹

This algorithm converges to the correct language in finite time from any text, which is exactly what identification in the limit requires. It never overgeneralizes beyond the target language (since it only permits $k$-grams it has evidence for), and it never gets permanently stuck on a sublanguage (since the finite set of permitted $k$-grams will eventually all be observed).

Why doesn’t Gold’s impossibility result apply? For a fixed finite alphabet and fixed $k$, there are only finitely many subsets of the finite set of possible $k$-grams, so there are only finitely many SL-$k$ hypotheses. This finite class is not superfinite and can be identified by the attested-factor learner. In contrast, the unbounded union $\mathrm{SL}=\bigcup_k\mathrm{SL}_k$ contains every finite language as well as infinite languages, so Gold’s obstruction applies to that unrestricted class (Gold 1967). A learner must instead receive a bound on $k$, additional information, or some other restriction on its hypothesis space. The operative contrast is superfinite versus restricted hypothesis spaces, not the mere presence of an ascending chain.

Learning SP languages

The algorithm for SP languages is entirely parallel. An SP-$k$ language is determined by a set of forbidden $k$-subsequences $\mathcal{F}$: a string is in the language if and only if none of the forbidden subsequences appear as subsequences of the string.

The learning algorithm:

Initialize $\mathcal{A} = \emptyset$ (attested subsequences of length at most $k$).
For each new example $w_i$, extract all subsequences of $w_i$ whose lengths are at most $k$ and add them to $\mathcal{A}$.
The current hypothesis is the SP-$k$ language with forbidden subsequences $\mathcal{F} = \Sigma^{\leq k} \setminus \mathcal{A}$, where $\Sigma^{\leq k}=\bigcup_{j=0}^k\Sigma^j$.

The convergence argument is the same: $\Sigma^{\leq k}$ is finite, so after enough examples all permitted subsequences will have been observed and the hypothesis stabilizes.² The shorter lengths matter. With $k=2$, the positive example a contributes both $\epsilon$ and a; an exact-length-2 extractor contributes nothing and thus loses evidence about short strings.

Learning TSL languages

Jardine and Heinz (2016) address TSL-$2$, not unrestricted TSL-$k$. Their Tier-based Strictly 2-Local Inference Algorithm (2TSLIA) assumes a fixed finite ordered alphabet and $k=2$. It computes paths recording two endpoints and the symbols intervening between them, begins with the entire alphabet on the hypothesized tier, and removes a symbol only when the paper’s path conditions identify it as a free non-tier element rather than an exclusive blocker. The algorithm then records the attested adjacent pairs on the resulting tier.

The polynomial identification result depends on a characteristic sample with evidence for (i) each non-tier symbol, (ii) each exclusive blocker, and (iii) each permitted tier $2$-factor. Under those conditions, 2TSLIA learns both a canonical tier and its permitted pairs from positive data. The result does not supply a generic tier-discovery procedure for arbitrary $k$.

The broader picture

Heinz and Rogers (2013) provided a general framework that unifies these algorithms using factored deterministic automata: each subregular class corresponds to a particular way of factoring the state space of a DFA, and the learning algorithm for each class exploits the corresponding factorization to learn from positive data. Lambert et al. (2021) argued that the convergence between learnability and typology is not a coincidence. On this view, the distributional properties of subregular classes predict which patterns should be common cross-linguistically.

The narrower picture is that positive-data learnability may help explain why some phonological pattern classes cluster near the bottom of the subregular hierarchy. The results reviewed here support that hypothesis for parameter-bounded families and specified data conditions. They do not derive the full typological distribution or show that human learners must use these particular algorithms.

References

Gold, E. Mark. 1967. “Language Identification in the Limit.” Information and Control 10 (5): 447–74. https://doi.org/10.1016/S0019-9958(67)91165-5.

Graf, Thomas. 2017. “The Power of Locality Domains in Phonology.” Phonology 34 (2): 385–405. https://doi.org/10.1017/S0952675717000197.

Heinz, Jeffrey. 2010. “Learning Long-Distance Phonotactics.” Linguistic Inquiry 41 (4): 623–61. https://doi.org/10.1162/LING\_a\_00015.

Heinz, Jeffrey. 2018. “The Computational Nature of Phonological Generalizations.” In Phonological Typology, edited by Larry M. Hyman and Frans Plank. De Gruyter Mouton. https://doi.org/10.1515/9783110451931-005.

Heinz, Jeffrey, Chetan Rawal, and Herbert G. Tanner. 2011. “Tier-Based Strictly Local Constraints for Phonology.” Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 58–64.

Heinz, Jeffrey, and James Rogers. 2013. “Learning Subregular Classes of Languages with Factored Deterministic Automata.” Proceedings of the 13th Meeting on Mathematics of Language (MOL), 64–71.

Jardine, Adam, and Jeffrey Heinz. 2016. “Learning Tier-Based Strictly 2-Local Languages.” Transactions of the Association for Computational Linguistics 4: 87–98. https://doi.org/10.1162/tacl\_a\_00085.

Lambert, Dakotah, Jonathan Rawski, and Jeffrey Heinz. 2021. “Typology Emerges from Simplicity in Representations and Learning.” J. Language Modelling 9 (1): 151–94. https://doi.org/10.15398/jlm.v9i1.262.

McNaughton, Robert, and Seymour A. Papert. 1971. Counter-Free Automata. M.i.t. Research Monograph 65. The MIT Press.

Rogers, James, Jeffrey Heinz, Gil Bailey, et al. 2010. “On Languages Piecewise Testable in the Strict Sense.” The Mathematics of Language, Lecture notes in artificial intelligence, vol. 6149: 255–65. https://doi.org/10.1007/978-3-642-14322-9\_19.

Rogers, James, Jeffrey Heinz, Margaret Fero, Jeremy Hurst, Dakotah Lambert, and Sean Wibel. 2013. “Cognitive and Sub-Regular Complexity.” Formal Grammar, Lecture notes in computer science, vol. 8036: 90–108. https://doi.org/10.1007/978-3-642-39998-5\_6.

Schützenberger, Marcel-Paul. 1965. “On Finite Monoids Having Only Trivial Subgroups.” Information and Control 8 (2): 190–94. https://doi.org/10.1016/S0019-9958(65)90108-7.

Footnotes

More precisely: since $L$ is SL-$k$, its set of permitted $k$-grams is exactly the set of $k$-grams that appear in strings in $L$. Any text for $L$—any sequence that eventually includes every string in $L$—will thus eventually present every permitted $k$-gram. Once all permitted $k$-grams have been seen, $\mathcal{A}$ equals the true set of permitted $k$-grams, $\mathcal{F}$ equals the true set of forbidden $k$-grams, and the hypothesis is correct. It will never change again, because no future example can introduce a $k$-gram not already in $\mathcal{A}$.↩︎
Extracting the subsequences of lengths at most $k$ from a string of length $n$ takes $O(\sum_{j=0}^k\binom{n}{j})$ time, which is polynomial in $n$ for fixed $k$.↩︎

--- title: Star-free languages and the full picture bibliography: ../../references.bib jupyter: python3 --- We've now seen a local branch (SL $\subset$ LT), a piecewise branch (SP $\subset$ PT), and TSL crosscutting both. What class contains these branches but still excludes some regular languages? The answer is the *star-free languages*. ## Star-free languages A language is *star-free* if it can be described by a generalized regular expression that uses union, concatenation, and *complement* but not Kleene star [@mcnaughton1971counter; @schutzenberger1965finite]. That is, we replace the $*$ operation with $\overline{\cdot}$ (complement with respect to $\Sigma^*$). Why is every star-free language regular? Use structural induction on a star-free expression. Start with the atomic languages $\emptyset$, $\{\epsilon\}$, and $\{a\}$ for $a\in\Sigma$, all of which are regular. Now suppose the immediate subexpressions describe regular languages. Their union and concatenation are regular by the constructions from the preceding sections, and the complement of either one is regular after determinization and completion. Each licensed star-free constructor thus preserves regularity. Since every star-free expression has a finite construction, its language is regular. This change carves out a particular subclass of the regular languages. In the presence of complement, removing Kleene star rules out the cyclic behavior needed for modular counting. For instance, the language $\{w \in \{a, b\}^* \mid |w|_a \equiv 0 \pmod{2}\}$—strings with an even number of $a$'s—is regular (you can build a two-state DFA for it) but not star-free. This does not mean that every regular expression containing a star performs modular counting; it means that some regular languages requiring modular counting have no star-free description. We can build star-free expressions using `arcweight` by constructing automata with `union`, `concat`, and `difference` (complement) only. ```{python} #| code-fold: true #| code-summary: Build a star-free language using only union, concatenation, and complement import arcweight # Alphabet: {a, b} syms = arcweight.SymbolTable() syms.add_symbol('<eps>') a = syms.add_symbol('a') b = syms.add_symbol('b') # Sigma-star: accepts all strings over {a, b} sigma_star = arcweight.VectorFst() s = sigma_star.add_state() sigma_star.set_start(s) sigma_star.set_final(s, 0.0) sigma_star.add_arc(s, a, a, 0.0, s) sigma_star.add_arc(s, b, b, 0.0, s) # Single-symbol FSAs fst_a = arcweight.VectorFst() s0 = fst_a.add_state() s1 = fst_a.add_state() fst_a.set_start(s0) fst_a.set_final(s1, 0.0) fst_a.add_arc(s0, a, a, 0.0, s1) fst_b = arcweight.VectorFst() s0 = fst_b.add_state() s1 = fst_b.add_state() fst_b.set_start(s0) fst_b.set_final(s1, 0.0) fst_b.add_arc(s0, b, b, 0.0, s1) # A star-free description may use Σ* because Σ* = complement(∅). # We construct the empty-language acceptor first to make that identity explicit. empty = arcweight.VectorFst() s = empty.add_state() empty.set_start(s) # No final state: this machine accepts nothing. # `arcweight.difference` requires an explicit machine for the ambient universe, # so the executable code uses `sigma_star` above to compute complements. # "Strings that contain [ab] as a substring" (star-free): # Σ* ∘ {a} ∘ {b} ∘ Σ* — but this uses concatenation, not star. # We concatenate with sigma_star (= complement(∅)) on both sides. ab_substr = arcweight.concat( arcweight.concat(sigma_star, fst_a), arcweight.concat(fst_b, sigma_star), ) # "Strings that do NOT contain [ab]" (complement of the above) no_ab = arcweight.difference(sigma_star, ab_substr) no_ab = arcweight.minimize(no_ab) print(f"no_ab states: {no_ab.num_states()}") ``` ### The McNaughton-Papert theorem @mcnaughton1971counter and @schutzenberger1965finite give an algebraic characterization of the star-free languages: a regular language is star-free if and only if its [syntactic monoid](https://en.wikipedia.org/wiki/Syntactic_monoid) is *aperiodic*, meaning it contains no nontrivial cyclic groups. The equivalent minimal-automaton statement is that a regular language is star-free if and only if its minimal DFA is [*counter-free*](https://en.wikipedia.org/wiki/Aperiodic_finite_automaton): there is no state $q$, nonempty string $w$, and integer $n > 1$ such that $\delta(q,w^n)=q$ but $\delta(q,w)\neq q$. In other words, if iterating some string $w$ cycles a state back to itself, then one application of $w$ must already return to that state. There is also a logical characterization: the star-free languages are exactly the languages definable in first-order logic with the linear order and successor predicates on string positions. This connects the subregular hierarchy to a broader program of relating language classes to logical expressiveness. We won't prove these equivalences here. For current purposes, their upshot is that the regular languages outside the star-free class require modular counting, while no known phonological pattern requires counting modulo a number. ## The complete hierarchy We can now assemble the full picture. The following containments are all proper: $$\text{SL}_k \subset \text{SL}_{k+1} \subset \ldots \subset \text{SL} \subset \text{LT} \subset \text{Star-Free} \subset \text{Regular}$$ $$\text{SP}_k \subset \text{SP}_{k+1} \subset \ldots \subset \text{SP} \subset \text{PT} \subset \text{Star-Free} \subset \text{Regular}$$ where SL $= \bigcup_k \text{SL}_k$ and SP $= \bigcup_k \text{SP}_k$. TSL sits on a third branch: it properly contains SL, is properly contained in the star-free languages, and is incomparable with LT and PT [@heinz2011tier]. Thus, the relationships among the branches are not captured by a single linear ordering. ::: {.callout-caution} ## Question The language "strings over $\{a, b\}$ with an even number of $a$'s" is regular. Is it star-free? ::: ::: {.callout-tip collapse=true} ## Answer No. This language requires counting $a$'s modulo 2, which requires a cyclic group in the syntactic monoid. The minimal DFA has two states that cycle with each $a$, making it a counter. Since the syntactic monoid is not aperiodic, the language is not star-free. ::: We can spell out the counter-free argument without computing the full syntactic monoid. A two-state DFA recognizes the language: let $q_{\mathrm{even}}$ be the initial and final state and $q_{\mathrm{odd}}$ the other state; `a` swaps them and `b` leaves them unchanged. This DFA is minimal. Both states are reachable, by $\epsilon$ and `a`, respectively. They are also distinguishable by the empty suffix: stopping in $q_{\mathrm{even}}$ accepts, while stopping in $q_{\mathrm{odd}}$ rejects. Thus, no equivalent DFA can merge them. And every string reaches one of the two states according to the parity of its number of `a`s, so the two states exhaust the equivalence classes. Now read one and then two copies of `a` from the even state: $$ \delta(q_{\mathrm{even}},a)=q_{\mathrm{odd}} \quad\text{but}\quad \delta(q_{\mathrm{even}},a^2)=q_{\mathrm{even}}. $$ Thus, the nonempty string $a$ forms a cycle of length $2$: applying it twice returns the state, while applying it once does not. The minimal DFA violates the counter-free condition, so the McNaughton-Papert theorem rules out any star-free description. ## The empirical picture Across the work cited here, attested phonological patterns tend to fall into the lower levels of this hierarchy [@heinz_computational_2018; @rogers2013cognitive; @lambert2021typology; @graf2017power]. - Most phonotactic constraints (restrictions on what sequences of sounds can appear) are SL—they depend on short contiguous contexts. - Long-distance phonological processes like harmony are typically SP or TSL. - Very few phonological patterns require even LT or PT. - No known phonological pattern requires the full power of the regular languages. There is nothing in the definition of a DFA that prevents a phonological pattern from using modular counting or other non-star-free capabilities. That phonological patterns don't use them is an empirical observation about natural language, not a logical necessity. ## Learnability revisited One candidate explanation for why phonological patterns cluster in the subregular hierarchy comes from learnability. Recall [Gold's result](../the-generativist-conceit.qmd): over a fixed nonempty finite alphabet $\Sigma$, if a hypothesis class contains every finite subset of $\Sigma^*$ and at least one infinite language, no learner can identify every member of that class in the limit from arbitrary positive text [@gold1967language]. The regular languages meet this condition. If particular restricted subregular families are identifiable from positive data, their learnability may help explain why phonological patterns cluster there. The scope of the positive results matters. @heinz2010learning describes the simple factor learner for SL-$k$ when $k$ is known in advance and proves positive-data identification for precedence languages, which correspond to SP-$2$ [see also @rogers2010languages]. The constructions below likewise hold a finite alphabet and $k$ fixed. They do not establish that every unbounded union—or every class in the hierarchy—is identifiable from positive data. ### Learning SL languages Recall from the [section on SL languages](local-languages.qmd) that an SL-$k$ language is determined by a set of forbidden $k$-grams $\mathcal{F}$: a string is in the language if and only if none of its $k$-grams (in the boundary-augmented string) appear in $\mathcal{F}$. The learning algorithm exploits this directly. Given a parameter $k$ and a stream of positive examples $w_1, w_2, \ldots$ from an unknown SL-$k$ language $L$: 1. Initialize $\mathcal{A} = \emptyset$ (the set of *attested* $k$-grams). 2. For each new example $w_i$, extract all $k$-grams from the augmented string $\rtimes^{k-1} w_i \ltimes^{k-1}$ and add them to $\mathcal{A}$. 3. At any point, the learner's current hypothesis is the SL-$k$ language with forbidden factors $\mathcal{F} = (\Sigma \cup \{\rtimes, \ltimes\})^k \setminus \mathcal{A}$—that is, every $k$-gram that has *not yet been observed* is assumed forbidden. The learner starts maximally restrictive (everything is forbidden) and relaxes constraints as it sees evidence. Since the alphabet is finite, there are only finitely many possible $k$-grams. After enough examples, every $k$-gram that is licit in $L$ will have been observed at least once, and the learner's hypothesis will stabilize at $L$.^[More precisely: since $L$ is SL-$k$, its set of permitted $k$-grams is exactly the set of $k$-grams that appear in strings in $L$. Any [text](../the-generativist-conceit.qmd) for $L$—any sequence that eventually includes every string in $L$—will thus eventually present every permitted $k$-gram. Once all permitted $k$-grams have been seen, $\mathcal{A}$ equals the true set of permitted $k$-grams, $\mathcal{F}$ equals the true set of forbidden $k$-grams, and the hypothesis is correct. It will never change again, because no future example can introduce a $k$-gram not already in $\mathcal{A}$.] This algorithm converges to the correct language in finite time from any text, which is exactly what [identification in the limit](https://en.wikipedia.org/wiki/Language_identification_in_the_limit) requires. It never overgeneralizes beyond the target language (since it only permits $k$-grams it has evidence for), and it never gets permanently stuck on a sublanguage (since the finite set of permitted $k$-grams will eventually all be observed). Why doesn't Gold's impossibility result apply? For a fixed finite alphabet and fixed $k$, there are only finitely many subsets of the finite set of possible $k$-grams, so there are only finitely many SL-$k$ hypotheses. This finite class is not superfinite and can be identified by the attested-factor learner. In contrast, the unbounded union $\mathrm{SL}=\bigcup_k\mathrm{SL}_k$ contains every finite language as well as infinite languages, so Gold's obstruction applies to that unrestricted class [@gold1967language]. A learner must instead receive a bound on $k$, additional information, or some other restriction on its hypothesis space. The operative contrast is superfinite versus restricted hypothesis spaces, not the mere presence of an ascending chain. ### Learning SP languages The algorithm for SP languages is entirely parallel. An SP-$k$ language is determined by a set of forbidden $k$-*subsequences* $\mathcal{F}$: a string is in the language if and only if none of the forbidden subsequences appear as subsequences of the string. The learning algorithm: 1. Initialize $\mathcal{A} = \emptyset$ (attested subsequences of length at most $k$). 2. For each new example $w_i$, extract all subsequences of $w_i$ whose lengths are at most $k$ and add them to $\mathcal{A}$. 3. The current hypothesis is the SP-$k$ language with forbidden subsequences $\mathcal{F} = \Sigma^{\leq k} \setminus \mathcal{A}$, where $\Sigma^{\leq k}=\bigcup_{j=0}^k\Sigma^j$. The convergence argument is the same: $\Sigma^{\leq k}$ is finite, so after enough examples all permitted subsequences will have been observed and the hypothesis stabilizes.^[Extracting the subsequences of lengths at most $k$ from a string of length $n$ takes $O(\sum_{j=0}^k\binom{n}{j})$ time, which is polynomial in $n$ for fixed $k$.] The shorter lengths matter. With $k=2$, the positive example `a` contributes both $\epsilon$ and `a`; an exact-length-2 extractor contributes nothing and thus loses evidence about short strings. ### Learning TSL languages @jardine2016learning address TSL-$2$, not unrestricted TSL-$k$. Their Tier-based Strictly 2-Local Inference Algorithm (2TSLIA) assumes a fixed finite ordered alphabet and $k=2$. It computes paths recording two endpoints and the symbols intervening between them, begins with the entire alphabet on the hypothesized tier, and removes a symbol only when the paper's path conditions identify it as a free non-tier element rather than an exclusive blocker. The algorithm then records the attested adjacent pairs on the resulting tier. The polynomial identification result depends on a characteristic sample with evidence for (i) each non-tier symbol, (ii) each exclusive blocker, and (iii) each permitted tier $2$-factor. Under those conditions, 2TSLIA learns both a canonical tier and its permitted pairs from positive data. The result does not supply a generic tier-discovery procedure for arbitrary $k$. ### The broader picture @heinz2013learning provided a general framework that unifies these algorithms using *factored deterministic automata*: each subregular class corresponds to a particular way of factoring the state space of a DFA, and the learning algorithm for each class exploits the corresponding factorization to learn from positive data. @lambert2021typology argued that the convergence between learnability and typology is not a coincidence. On this view, the distributional properties of subregular classes predict which patterns should be common cross-linguistically. The narrower picture is that positive-data learnability may help explain why some phonological pattern classes cluster near the bottom of the subregular hierarchy. The results reviewed here support that hypothesis for parameter-bounded families and specified data conditions. They do not derive the full typological distribution or show that human learners must use these particular algorithms.