In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.
An archetypical context-free language is , 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 , and is accepted by the p...
more
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.
An archetypical context-free language is , 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 , and is accepted by the pushdown automaton M = ({q0,q1,qf},{a,b},{a,z},δ,q0,{qf}) where δ is defined as follows:
δ(q0,a,z) = (q0,a)
δ(q0,a,a) = (q0,a)
δ(q0,b,a) = (q1,x)
δ(q1,b,a) = (q1,x)
δ(q1,λ,z) = (qf,z)
δ(state1,read,pop) = (state2,push)
where z is initial stack symbol and x means pop action.
Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar . Also, most arithmetic expressions are generated by context-free grammars.
Context-free languages are closed...
less
