Definition 4.1.3: For grammar G = (V, _, P, S) the language defined by G, is L(G) = {x___* | S _* x}, and a language for which such a grammar exists is called a phrase structure language. Two grammars G1 and G2 are equivalent if L(G1) = L(G2).
Example 4.1.1. Consider G where V = {S}, _ = {a, b}, and P = {S _ aSb, S _ ab}. Then for derivations we have a doubly infinite set of possibilities
S _ aSb _ aaSbb _ __________ _ _ ab aabb aaabbb
as there are two permissible rewritings at each point. Hence L(G) = {anbn | n1}.
| Previous slide | Next slide | Back to first slide | View graphic version |