# Context-free language

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Context-free_language
> Markdown URL: https://mediated.wiki/source/Context-free_language.md
> Source: https://en.wikipedia.org/wiki/Context-free_language
> Source revision: 1353323604
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Formal language generated by context-free grammar

In [formal language theory](/source/Formal_language_theory), a **context-free language** (**CFL**), also called a **[Chomsky](/source/Chomsky_hierarchy) type-2 language**, is a [language](/source/Formal_language) generated by a [context-free grammar](/source/Context-free_grammar) (CFG).

Context-free languages have many applications in [programming languages](/source/Programming_languages), in particular, most arithmetic expressions are generated by context-free grammars.

## Background

### Context-free grammar

Different context-free grammars can generate the same context-free language. Intrinsic properties of the language can be distinguished from extrinsic properties of a particular grammar by comparing multiple grammars that describe the language.

### Automata

The set of all context-free languages is identical to the set of languages accepted by [pushdown automata](/source/Pushdown_automata), which makes these languages amenable to parsing. Further, for a given CFG, there is a direct way to produce a pushdown automaton for the grammar (and thereby the corresponding language), though going the other way (producing a grammar given an automaton) is not as direct.

## Examples

An example context-free language is L = { a n b n : n ≥ 1 } {\displaystyle L=\{a^{n}b^{n}:n\geq 1\}} , the language of all non-empty even-length strings, the entire first halves of which are a's, and the entire second halves of which are b's. L is generated by the grammar S → a S b | a b {\displaystyle S\to aSb~|~ab} . This language is not regular. It is accepted by the pushdown automaton M = ( { q 0 , q 1 , q f } , { a , b } , { a , z } , δ , q 0 , z , { q f } ) {\textstyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})} where δ {\displaystyle \delta } is defined as follows:[note 1]

- δ ( q 0 , a , z ) = ( q 0 , a z ) δ ( q 0 , a , a ) = ( q 0 , a a ) δ ( q 0 , b , a ) = ( q 1 , ε ) δ ( q 1 , b , a ) = ( q 1 , ε ) δ ( q 1 , ε , z ) = ( q f , ε ) {\displaystyle {\begin{aligned}\delta (q_{0},a,z)&=(q_{0},az)\\\delta (q_{0},a,a)&=(q_{0},aa)\\\delta (q_{0},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},\varepsilon ,z)&=(q_{f},\varepsilon )\end{aligned}}}

Unambiguous CFLs are a proper subset of all CFLs: there are inherently ambiguous CFLs. An example of an inherently ambiguous CFL is the union of { a n b m c m d n | n , m > 0 } {\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}} with { a n b n c m d m | n , m > 0 } {\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}} . This set is context-free, since the union of two context-free languages is always context-free. But there is no way to unambiguously parse strings in the (non-context-free) subset { a n b n c n d n | n > 0 } {\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}} which is the intersection of these two languages.[1]

### Dyck language

The language of all properly matched parentheses is generated by the grammar S → S S | ( S ) | ε {\displaystyle S\to SS~|~(S)~|~\varepsilon } .

## Properties

### Context-free parsing

Main article: [Parsing](/source/Parsing)

The context-free nature of the language makes it simple to parse with a pushdown automaton.

Determining an instance of the [membership problem](https://en.wikipedia.org/w/index.php?title=Membership_problem&action=edit&redlink=1); i.e. given a string w {\displaystyle w} , determine whether w ∈ L ( G ) {\displaystyle w\in L(G)} where L {\displaystyle L} is the language generated by a given grammar G {\displaystyle G} ; is also known as *recognition*. Context-free recognition for [Chomsky normal form](/source/Chomsky_normal_form) grammars was shown by [Leslie G. Valiant](/source/Leslie_Valiant) to be reducible to Boolean [matrix multiplication](/source/Matrix_multiplication), thus inheriting its complexity upper bound of [*O*](/source/Big_O_notation)(*n*2.3728596).[2][note 2] Conversely, [Lillian Lee](/source/Lillian_Lee_(computer_scientist)) has shown *O*(*n*3−ε) Boolean matrix multiplication to be reducible to *O*(*n*3−3ε) CFG parsing, thus establishing some kind of lower bound for the latter.[3]

Practical uses of context-free languages require also to produce a derivation tree that exhibits the structure that the grammar associates with the given string. The process of producing this tree is called *[parsing](/source/Parsing)*. Known parsers have a time complexity that is cubic in the size of the string that is parsed.

Formally, the set of all context-free languages is identical to the set of languages accepted by pushdown automata (PDA). Parser algorithms for context-free languages include the [CYK algorithm](/source/CYK_algorithm) and [Earley's Algorithm](/source/Earley_parser).

A special subclass of context-free languages are the [deterministic context-free languages](/source/Deterministic_context-free_language) which are defined as the set of languages accepted by a [deterministic pushdown automaton](/source/Deterministic_pushdown_automaton) and can be parsed by a [LR(k) parser](/source/LR_parser).[4]

See also [parsing expression grammar](/source/Parsing_expression_grammar) as an alternative approach to grammar and parser.

### Closure properties

The class of context-free languages is [closed](/source/Closure_(mathematics)) under the following operations. That is, if *L* and *P* are context-free languages, the following languages are context-free as well:

- the [union](/source/Union_(set_theory)) L ∪ P {\displaystyle L\cup P} of *L* and *P*[5]

- the reversal of *L*[6]

- the [concatenation](/source/Concatenation) L ⋅ P {\displaystyle L\cdot P} of *L* and *P*[5]

- the [Kleene star](/source/Kleene_star) L ∗ {\displaystyle L^{*}} of *L*[5]

- the image φ ( L ) {\displaystyle \varphi (L)} of *L* under a [homomorphism](/source/String_operations#String_homomorphism) φ {\displaystyle \varphi } [7]

- the image φ − 1 ( L ) {\displaystyle \varphi ^{-1}(L)} of *L* under an [inverse homomorphism](/source/String_operations#String_homomorphism) φ − 1 {\displaystyle \varphi ^{-1}} [8]

- the [circular shift](/source/Circular_shift#Applications) of *L* (the language { v u : u v ∈ L } {\displaystyle \{vu:uv\in L\}} )[9]

- the prefix closure of *L* (the set of all [prefixes](/source/Prefix_(computer_science)) of strings from *L*)[10]

- the [quotient](/source/Quotient_of_a_formal_language) *L*/*R* of *L* by a regular language *R*[11]

#### Nonclosure under intersection, complement, and difference

The context-free languages are not closed under intersection. This can be seen by taking the languages A = { a n b n c m ∣ m , n ≥ 0 } {\displaystyle A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}} and B = { a m b n c n ∣ m , n ≥ 0 } {\displaystyle B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}} , which are both context-free.[note 3] Their intersection is A ∩ B = { a n b n c n ∣ n ≥ 0 } {\displaystyle A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}} , which can be shown to be non-context-free by the [pumping lemma for context-free languages](/source/Pumping_lemma_for_context-free_languages). As a consequence, context-free languages cannot be closed under complementation, as for any languages *A* and *B*, their intersection can be expressed by union and complement: A ∩ B = A ¯ ∪ B ¯ ¯ {\displaystyle A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}} . In particular, context-free language cannot be closed under difference, since complement can be expressed by difference: L ¯ = Σ ∗ ∖ L {\displaystyle {\overline {L}}=\Sigma ^{*}\setminus L} .[12]

However, if *L* is a context-free language and *D* is a regular language then both their intersection L ∩ D {\displaystyle L\cap D} and their difference L ∖ D {\displaystyle L\setminus D} are context-free languages.[13]

### Decidability

In formal language theory, questions about regular languages are usually decidable, but ones about context-free languages are often not. It is decidable whether such a language is finite, but not whether it contains every possible string, is regular, is unambiguous, or is equivalent to a language with a different grammar.

The following problems are [undecidable](/source/Undecidable_problem) for arbitrarily given [context-free grammars](/source/Context-free_grammar) A and B:

- Equivalence: is L ( A ) = L ( B ) {\displaystyle L(A)=L(B)} ?[14]

- Disjointness: is L ( A ) ∩ L ( B ) = ∅ {\displaystyle L(A)\cap L(B)=\emptyset } ?[15] However, the intersection of a context-free language and a *regular* language is context-free,[16][17] hence the variant of the problem where *B* is a regular grammar is decidable (see "Emptiness" below).

- Containment: is L ( A ) ⊆ L ( B ) {\displaystyle L(A)\subseteq L(B)} ?[18] Again, the variant of the problem where *B* is a regular grammar is decidable,[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*] while that where *A* is regular is generally not.[19]

- Universality: is L ( A ) = Σ ∗ {\displaystyle L(A)=\Sigma ^{*}} ?[20]

- Regularity: is L ( A ) {\displaystyle L(A)} a regular language?[21]

- Ambiguity: is every grammar for L ( A ) {\displaystyle L(A)} ambiguous?[22]

The following problems are *decidable* for arbitrary context-free languages:

- Emptiness: Given a context-free grammar *A*, is L ( A ) = ∅ {\displaystyle L(A)=\emptyset } ?[23]

- Finiteness: Given a context-free grammar *A*, is L ( A ) {\displaystyle L(A)} finite?[24]

- Membership: Given a context-free grammar *G*, and a word w {\displaystyle w} , does w ∈ L ( G ) {\displaystyle w\in L(G)} ? Efficient polynomial-time algorithms for the membership problem are the [CYK algorithm](/source/CYK_algorithm) and [Earley's Algorithm](/source/Earley_parser).

According to [Hopcroft](/source/John_Hopcroft), [Motwani](/source/Rajeev_Motwani), [Ullman](/source/Jeffrey_Ullman) (2006),[25] many of the fundamental closure and (un)decidability properties of context-free languages were shown in the 1961 paper of [Bar-Hillel](/source/Yehoshua_Bar-Hillel), Perles, and Shamir.[26]

### Languages that are not context-free

The set { a n b n c n d n | n > 0 } {\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}} is a [context-sensitive language](/source/Context-sensitive_language), but there does not exist a context-free grammar generating this language.[27] So there exist context-sensitive languages which are not context-free. To prove that a given language is not context-free, one may employ the [pumping lemma for context-free languages](/source/Pumping_lemma_for_context-free_languages)[26] or a number of other methods, such as [Ogden's lemma](/source/Ogden's_lemma) or [Parikh's theorem](/source/Parikh's_theorem).[28]

## Notes

1. **[^](#cite_ref-1)** meaning of δ {\displaystyle \delta } 's arguments and results: δ ( s t a t e 1 , r e a d , p o p ) = ( s t a t e 2 , p u s h ) {\displaystyle \delta (\mathrm {state} _{1},\mathrm {read} ,\mathrm {pop} )=(\mathrm {state} _{2},\mathrm {push} )}

1. **[^](#cite_ref-4)** In Valiant's paper, *O*(*n*2.81) was the then-best known upper bound. See [Matrix multiplication#Computational complexity](/source/Matrix_multiplication#Computational_complexity) for bound improvements since then.

1. **[^](#cite_ref-14)** A context-free grammar for the language *A* is given by the following production rules, taking *S* as the start symbol: *S* → *Sc* | *aTb* | *ε*; *T* → *aTb* | *ε*. The grammar for *B* is analogous.

## References

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979100Theorem_4.7_2-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 100, Theorem 4.7.

1. **[^](#cite_ref-FOOTNOTEValiant1975_3-0)** [Valiant 1975](#CITEREFValiant1975).

1. **[^](#cite_ref-FOOTNOTELee2002_5-0)** [Lee 2002](#CITEREFLee2002).

1. **[^](#cite_ref-FOOTNOTEKnuth1965_6-0)** [Knuth 1965](#CITEREFKnuth1965).

1. ^ [***a***](#cite_ref-FOOTNOTEHopcroftUllman1979131Corollary_of_Theorem_6.1_7-0) [***b***](#cite_ref-FOOTNOTEHopcroftUllman1979131Corollary_of_Theorem_6.1_7-1) [***c***](#cite_ref-FOOTNOTEHopcroftUllman1979131Corollary_of_Theorem_6.1_7-2) [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 131, Corollary of Theorem 6.1.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979142Exercise_6.4d_8-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 142, Exercise 6.4d.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979131-132Corollary_of_Theorem_6.2_9-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 131-132, Corollary of Theorem 6.2.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979132Theorem_6.3_10-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 132, Theorem 6.3.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979142-144Exercise_6.4c_11-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 142-144, Exercise 6.4c.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979142Exercise_6.4b_12-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 142, Exercise 6.4b.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979142Exercise_6.4a_13-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 142, Exercise 6.4a.

1. **[^](#cite_ref-FOOTNOTEScheinberg1960_15-0)** [Scheinberg 1960](#CITEREFScheinberg1960).

1. **[^](#cite_ref-FOOTNOTEBeigelGasarch_16-0)** [Beigel & Gasarch](#CITEREFBeigelGasarch).

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979203Theorem_8.12(1)_17-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 203, Theorem 8.12(1).

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979202Theorem_8.10_18-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 202, Theorem 8.10.

1. **[^](#cite_ref-FOOTNOTESalomaa197359Theorem_6.7_19-0)** [Salomaa 1973](#CITEREFSalomaa1973), p. 59, Theorem 6.7.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979135Theorem_6.5_20-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 135, Theorem 6.5.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979203Theorem_8.12(2)_21-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 203, Theorem 8.12(2).

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979203Theorem_8.12(4)_22-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 203, Theorem 8.12(4).

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979203Theorem_8.11_23-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 203, Theorem 8.11.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979205Theorem_8.15_24-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 205, Theorem 8.15.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979206Theorem_8.16_25-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 206, Theorem 8.16.

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979137Theorem_6.6(a)_26-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 137, Theorem 6.6(a).

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979137Theorem_6.6(b)_27-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979), p. 137, Theorem 6.6(b).

1. **[^](#cite_ref-FOOTNOTEHopcroftMotwaniUllman2006See_Section_7.6_for_properties_of_context-free_languages_and_Section_9.7_for_related_exercises_28-0)** [Hopcroft, Motwani & Ullman 2006](#CITEREFHopcroftMotwaniUllman2006), See Section 7.6 for properties of context-free languages and Section 9.7 for related exercises.

1. ^ [***a***](#cite_ref-FOOTNOTEBar-HillelPerlesShamir1961_29-0) [***b***](#cite_ref-FOOTNOTEBar-HillelPerlesShamir1961_29-1) [Bar-Hillel, Perles & Shamir 1961](#CITEREFBar-HillelPerlesShamir1961).

1. **[^](#cite_ref-FOOTNOTEHopcroftUllman1979_30-0)** [Hopcroft & Ullman 1979](#CITEREFHopcroftUllman1979).

1. **[^](#cite_ref-31)** Stack Exchange. ["How to prove that a language is not context-free?"](https://cs.stackexchange.com/q/265).

### Works cited

- [Bar-Hillel, Yehoshua](/source/Yehoshua_Bar-Hillel); Perles, Micha Asher; Shamir, Eli (1961). "On Formal Properties of Simple Phrase-Structure Grammars". *Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung*. **14** (2): 143–172.

- Beigel, Richard; [Gasarch, William](/source/William_Gasarch). ["A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA's"](http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf) (PDF). *University of Maryland Department of Computer Science*. [Archived](https://web.archive.org/web/20141212060332/http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf) (PDF) from the original on 12 December 2014. Retrieved 6 June 2020.

- [Hopcroft, John E.](/source/John_Hopcroft); [Ullman, Jeffrey D.](/source/Jeffrey_Ullman) (1979). *[Introduction to Automata Theory, Languages, and Computation](/source/Introduction_to_Automata_Theory%2C_Languages%2C_and_Computation)* (1st ed.). Addison-Wesley. [ISBN](/source/ISBN_(identifier)) [0-201-02988-X](https://en.wikipedia.org/wiki/Special:BookSources/0-201-02988-X). ([accessible to patrons with print disabilities](https://archive.org/details/introductiontoau00hopc))

- [Hopcroft, John E.](/source/John_Hopcroft); [Motwani, Rajeev](/source/Rajeev_Motwani); [Ullman, Jeffrey D.](/source/Jeffrey_Ullman) (2006) [1979]. *[Introduction to Automata Theory, Languages, and Computation](/source/Introduction_to_Automata_Theory%2C_Languages%2C_and_Computation)* (3rd ed.). Addison-Wesley. [ISBN](/source/ISBN_(identifier)) [0-321-45536-3](https://en.wikipedia.org/wiki/Special:BookSources/0-321-45536-3).

- [Knuth, D. E.](/source/Donald_Knuth) (July 1965). "On the translation of languages from left to right". *Information and Control*. **8** (6): 607–639. [doi](/source/Doi_(identifier)):[10.1016/S0019-9958(65)90426-2](https://doi.org/10.1016%2FS0019-9958%2865%2990426-2).

- [Lee, Lillian](/source/Lillian_Lee_(computer_scientist)) (January 2002). ["Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication"](https://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf) (PDF). *J ACM*. **49** (1): 1–15. [arXiv](/source/ArXiv_(identifier)):[cs/0112018](https://arxiv.org/abs/cs/0112018). [doi](/source/Doi_(identifier)):[10.1145/505241.505242](https://doi.org/10.1145%2F505241.505242). [S2CID](/source/S2CID_(identifier)) [1243491](https://api.semanticscholar.org/CorpusID:1243491). [Archived](https://web.archive.org/web/20030427152836/http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf) (PDF) from the original on 27 April 2003.

- [Salomaa, Arto](/source/Arto_Salomaa) (1973). *Formal Languages*. ACM Monograph Series. New York: Academic Press. [ISBN](/source/ISBN_(identifier)) [978-0126157505](https://en.wikipedia.org/wiki/Special:BookSources/978-0126157505).

- Scheinberg, Stephen (1960). ["Note on the Boolean Properties of Context Free Languages"](https://core.ac.uk/download/pdf/82210847.pdf) (PDF). *Information and Control*. **3** (4): 372–375. [doi](/source/Doi_(identifier)):[10.1016/s0019-9958(60)90965-7](https://doi.org/10.1016%2Fs0019-9958%2860%2990965-7). [Archived](https://web.archive.org/web/20181126005901/https://core.ac.uk/download/pdf/82210847.pdf) (PDF) from the original on 26 November 2018.

- [Valiant, Leslie G.](/source/Leslie_Valiant) (April 1975). ["General context-free recognition in less than cubic time"](https://figshare.com/articles/journal_contribution/General_context-free_recognition_in_less_than_cubic_time/6605915/1/files/12096398.pdf) (PDF). *Journal of Computer and System Sciences*. **10** (2): 308–315. [doi](/source/Doi_(identifier)):[10.1016/s0022-0000(75)80046-8](https://doi.org/10.1016%2Fs0022-0000%2875%2980046-8).

## Further reading

- Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Context-Free Languages and Push-Down Automata". In G. Rozenberg; A. Salomaa (eds.). [*Handbook of Formal Languages*](https://www-igm.univ-mlv.fr/~berstel/Articles/1997CFLPDA.pdf) (PDF). Vol. 1. Springer-Verlag. pp. 111–174. [Archived](https://web.archive.org/web/20110516030515/http://www-igm.univ-mlv.fr/%7Eberstel/Articles/1997CFLPDA.pdf) (PDF) from the original on 16 May 2011.

- [Ginsburg, Seymour](/source/Seymour_Ginsburg) (1966). *The Mathematical Theory of Context-Free Languages*. New York, NY, USA: McGraw-Hill.

- [Sipser, Michael](/source/Michael_Sipser) (1997). "**2**: Context-Free Languages". *[Introduction to the Theory of Computation](/source/Introduction_to_the_Theory_of_Computation)* (1st ed.). PWS Publishing. pp. 91–122. [ISBN](/source/ISBN_(identifier)) [978-0-534-94728-6](https://en.wikipedia.org/wiki/Special:BookSources/978-0-534-94728-6). ([accessible to patrons with print disabilities](https://archive.org/details/introductiontoth00sips))

v t e Automata theory: formal languages and formal grammars Chomsky hierarchy Grammars Languages Abstract machines Type-0 — Type-1 — — — — — Type-2 — — Type-3 — — Unrestricted (no common name) Context-sensitive Positive range concatenation Indexed — Linear context-free rewriting systems Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular — Non-recursive Recursively enumerable Decidable Context-sensitive Positive range concatenation* Indexed* — Linear context-free rewriting language Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular Star-free Finite Turing machine Decider Linear-bounded PTIME Turing Machine Nested stack Thread automaton restricted Tree stack automaton Embedded pushdown Nondeterministic pushdown Deterministic pushdown Visibly pushdown Finite Counter-free (with aperiodic finite monoid) Acyclic finite Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.

Authority control databases: National Czech Republic

---
Adapted from the Wikipedia article [Context-free language](https://en.wikipedia.org/wiki/Context-free_language) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Context-free_language?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.