Psychology Wiki

Context free language

34,203pages on
this wiki
Add New Page
Talk0 Share

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language | Individual differences | Personality | Philosophy | Social |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |

Language: Linguistics · Semiotics · Speech

A context-free language is a formal language that is accepted by some pushdown automaton. Context-free languages can be generated by context-free grammars.


An archetypical context-free language is L = \{a^nb^n:n\geq1\}, 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\to aSb ~|~ ab, and is accepted by the pushdown automaton M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\}) where \delta is defined as follows:

\delta(q_0, a, z) = (q_0, a)
\delta(q_0, b, ax) = (q_1, x)
\delta(q_1, b, ax) = (q_1, x)
\delta(q_1, b, bz) = (q_f, z)

Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar S\to SS ~|~ (S) ~|~ \lambda. Also, most arithmetic expressions are generated by context-free grammars.

Closure Properties Edit

Context-Free Languages are closed under the following operations. That is, if "L" and "P" are Context-Free Languages and "D" is a Regular Language, the following languages are Context-Free as well:

Context-Free Languages are not closed under complement, intersection, or difference.

See alsoEdit

There is a pumping lemma for context-free languages, that gives a necessary condition for a language to be context-free.

References Edit

Automata theory: formal languages and formal grammars
Grammars Languages Minimal
Type-0 Unrestricted Recursively enumerable Turing machine
n/a (no common name) Recursive Decider
Type-1 Context-sensitive Context-sensitive Linear-bounded
Type-2 Context-free Context-free Pushdown
Type-3 Regular Regular Finite
Each category of languages or grammars is a proper superset of the category directly beneath it.
cs:Bezkontextový jazyk

de:Kontextfreie Sprachehe:שפה חופשית הקשרro:Limbaje independente de context fi:Yhteydetön kieli

This page uses Creative Commons Licensed content from Wikipedia (view authors).

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Also on Fandom

Random Wiki