- English only

# Lab for Automated Reasoning and Analysis LARA

Here is general information on Context-free Grammars.

Typically, in a context-free grammar one can have multiple productions of the form

N -> w1 N -> w2 M -> w3 M -> w4 M -> w5

I use the notation that corresponds to Backus-Naur form which collects all right-hand sides correspondig to same left-hand sides and separate the alternatives using the “|” sign:

N ::= w1 | w2 M ::= w3 | w4 | w5

Note that, when we write, for example,

N ::= a | N + N

the two occurrences of N in “N + N” need not denote the same expression, they merely denote two subexpressions both of which conform to the syntax defined by N. Sometimes, to make this clear and to make it possible to refer to individual occurrences, we can write subscripts, as in

N ::= a | N_1 + N_2

using the convention that N_i denotes the same set of strings as N.