CFG

• Context-free grammars can generate context-free languages.

• They do this by taking a set of variables which are defined recursively, in terms of one another, by a set of production rules.

• Context-free grammars are named as such because any of the production rules in the grammar can be applied regardless of context—it does not depend on any other symbols that may or may not be around a given symbol that is having a rule applied to it.

Context-free grammars have the following components:

• A set of terminal symbols which are the characters that appear in the language/strings generated by the grammar. Terminal symbols never appear on the left-hand side of the production rule and are always on the right-hand side.

• A set of nonterminal symbols (or variables) which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols. These are the symbols that will always appear on the left-hand side of the production rules, though they can be included on the right-hand side. The strings that a CFG produces will contain only symbols from the set of nonterminal symbols.

• A set of production rules which are the rules for replacing nonterminal symbols. Production rules have the following form: variable \rightarrow→ string of variables and terminals.

• A start symbol which is a special nonterminal symbol that appears in the initial string generated by the grammar.

• For comparison, a context-sensitive grammar can have production rules where both the left-hand and right-hand sides may be surrounded by a context of terminal and nonterminal symbols.

To create a string from a context-free grammar, follow these steps:

• Begin the string with a start symbol.

• Apply one of the production rules to the start symbol on the left-hand side by replacing the start symbol with the right-hand side of the production.

• Repeat the process of selecting nonterminal symbols in the string, and replacing them with the right-hand side of some corresponding production, until all nonterminals have been replaced by terminal symbols. Note, it could be that not all production rules are used.

Formal Definition

A context-free grammar can be described by a four-element tuple (V, \Sigma, R, S),(V,Σ,R,S), where

• VV is a finite set of variables (which are non-terminal);
• \SigmaΣ is a finite set ((disjoint from V)V) of terminal symbols;
• RR is a set of production rules where each production rule maps a variable to a string s \in (V \cup \Sigma)*s∈(V∪Σ)∗;
• SS ((which is in V)V) which is a start symbol.

• Come up with a grammar that will generate the context-free (and also regular) language that contains all strings with matched parentheses.

  There are many grammars that can do this task. This solution is one way to do it, but should give you a good idea of if your (possibly different) solution works too.

  Starting symbol \rightarrow→ S
  Non-terminal variables = \{(,)\}{(,)}
  Production rules:

• S \rightarrow→ ( )
• S \rightarrow→ SS
• S \rightarrow→ (S). _\square□​
• A way to condense production rules is as follows:
• We can take

S \rightarrow→ ( )
S \rightarrow→ SS
S \rightarrow→ (S)

• and translate them into a single line: S \rightarrow→ ( ) | SS | (S) | \epsilon,ϵ, where \epsilonϵ is an empty string.
• Strings that end in 0Strings that have an odd number of 1’sStrings that have an equal number of 1’s and 0’sStrings that end in 1Strings that have an even number of 1’s and 0’s

 EX:   does the following context-free grammar describe?

• S is the start symbol and the set of nonterminal symbols is \{0,1\}{0,1}. Here are the production rules:
• S \rightarrow→ 0
• S \rightarrow→ 0S
• S \rightarrow→ 1S.

• Here is a context-free grammar that generates arithmetic expressions (subtraction, addition, division, and multiplication).

• Start symbol = <expression>

• Terminal symbols = \{+, -, *, /, (, ), \text{number}\},{+,−,∗,/,(,),number}, where “number” is any number

• Production rules:

  1. <expression> \rightarrow→ number
  2. <expression> \rightarrow→ (<expression>)
  3. <expression> \rightarrow→ <expression> + <expression>
  4. <expression> \rightarrow→ <expression> - <expression>
  5. <expression> \rightarrow→ <expression> * <expression>
  6. <expression> \rightarrow→ <expression> / <expression>

• This allows us to construct whatever expressions using multiplication, addition, division, and subtraction we want. What these production rules tell us is that the result of any operation, for example, multiplication, is also an expression (denoted, <expression>).