(www.cs.unc.edu) COMP 455 Links

ROAM_REFS: https://www.cs.unc.edu/~plaisted/comp455/slides/cfg3.1.pdf

• Context-Free Grammars

Context-free languages are useful for studying computer languages as well as human languages.

• Context-free languages are recognized by push-down automata (PDA) in the same way that regular languages are recognized by finite automata.
• A push-down automaton has an infinite amount of memory but it is only accessed in a last-in first-out (LIFO) manner, that is, like a stack.
• Thus push-down automata are more powerful than finite automata; for example, {anbn : n ≥ 0} is a context-free language.
• But push-down automata are less powerful than Turing machines, which we'll study later.
• Turing machines have an infinite amount of memory that can be accessed in an arbitrary manner.