Wikia

Psychology Wiki

Context free language

Talk0
34,139pages on
this wiki

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.

ExamplesEdit

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
Chomsky
hierarchy
Grammars Languages Minimal
automaton
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).

Around Wikia's network

Random Wiki