Context-free grammars

To insert a sample CFG into your document, select from the editor
Insert⟶ Structure⟶CFG.

A context-free grammar (CFG) is a grammar consisting of 4 components∶
Description
Math notation
Grafstate code
Set of variables (V)
V={S, A, B}.
V={S,A,B}
Input alphabet (Σ)
Σ={0,1}.
S={0,1}
Initial variable (v0)
v0=S.
v0=S
Grammar rules
A⟶0 A 1 ∣ iε
A->0 A 1 | \e
To begin the creation of a CFG, enter the command :+ cfg name. The syntax for the CFG code is as follows∶

Syntax constraints for a CFG

Each line and of a CFG is checked against the following constraints. If a line violates a constraint, then you will receive an error message.
V and S must be nonempty sets.
Each variable name must begin with an uppercase letter.
v0 must be defined as an element of V .
Each rule must have the form A-> w, where A is a variable (defined in V ) and w is either
1ε
2a single variable (defined in V ) or a single symbol (defined in S ),
3 TERM1 TERM2 ... where each term in the list TERM1, TERM2, … is either a variable (defined in V ) or a symbol (defined in S ).
Terms in the right-hand-side of a rule must be separated by spaces.
Each variable defined in V must be used as the left-hand-side of at lest one rule.
Each variable defined in V must be used in the right-hand-side of at lest one rule.

Abbreviated notation

You can write multiple rule expansions from a single variable on one line using the | symbol to join the expansions (the right-hand-sides) of the rules in the following way∶
A->0 A 1 | \e

The line above defines the following 2 rules∶
A -> 0 A 1
A -> \e

The line A -> 0 A 1 | \e is not read A expands to 0 followed by A followed by either 1 or ε. The correct interpretation is∶
 A can expand to either 0 A 1 or to ε.

Example

The following is a description of a CFG G that recognizes the language {anbn∶n≥0}. In other words, G derives strings having zero or more a 's followed by exactly the same number of b 's.
Context-free grammar
Variables V = {A}
Input alphabet Σ = {a,b}
Initial variable v0 = A
Rules
        A⟶a A b
        A⟶ε
G
G can be constructed using the following Grafstate code∶
Code
:+ cfg G
V={A`};
S={a,b`}.
v0=A;
A->a A b | \e;
done.

Simulating a CFG

The Grafstate Simulator will show all expansion steps that a CFG take when deriving an input string. If an input string w is derived by the a CFG, then the expansion steps are visualized in the simulation as 1 a left-most derivation and 2 a parse tree. Symbols from w that are read are shown in the parse tree as nodes with boxes. Variables in the expansion steps are shown in the parse tree as nodes without boxes.

The following Grafstate code simulates G (above) on the string aaabbb ∶
Code
:sim G aaabbb
Simulation
Input aaabbb
Result ACCEPTED
Explanation The left-most derivation is∶
        A ⟹ a A b ⟹ a a A b b ⟹ a a a A b b b ⟹ a a a b b b
Tree
Context-free grammar∶ G
If a string w is not derived by a CFG G, then the simulation will not show a parse tree or a left-most derivation. Instead, the Grafstate Simulator attempts to explain why w could not be derived by G.

The following Grafstate code simulates G on two strings ( abb and ][aab]) that cannot be derived by G∶
Code
:sim G abb
:sim G aab
Simulation
Input abb
Result REJECTED
Explanation The string abb cannot be read. Input can be read up to the highlighted b but no rules are available to read b. There are no alternate symbols that could be read past this point in the string.
Context-free grammar∶ G
Simulation
Input aab
Result REJECTED
Explanation The entire string can be read but the derivation from A is incomplete. More input would be needed to complete a derivation. However, there are no additional symbols that can be read past this point in the string.
Context-free grammar∶ G