Grammars are yet another way to define languages. A formal grammar is used to define a formal language. The following is a formal grammar defined for the language denoted by the a* regular expression:
The formal definition of a grammar is , where
V is a set of non-terminal symbols (e.g., in the grammar shown here).
Σ is an alphabet (e.g., ).
P is a finite set of production rules, each of the form χ → y, where ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month, and much more.
, where
in the grammar shown here).