Math and science::Theory of Computation

# Context-free languages

### Context-free languages

A context-free language is a language that [...].

Below, we define the pieces involved in this definition.

#### Grammar

A grammar can be considered an input datum of a specific type of string [what1?] that takes in input in the form of a list of [what2?].

Below are some examples of some [what2?]:

\begin{align*} S &\to aSb && (\text{context-free}) \\ S &\to AB && (\text{context-free}) \\ aA &\to C && (\text{not context-free}) \\ bAc &\to B && (\text{not context-free}) \\ CA &\to cA && (\text{not context-free}) \\ \end{align*}

A context-free grammar is one type of grammar.

### Context-free grammar (my definition)

A grammar is context-free iff [...].

See the back side for the standard definition and an explanation as to why I think it contains redundancies.

A quality of context-free grammars is that no matter what order rewrites are carried out, the same language will be generated.

#### The implicit grammar machine

In my opinion, the concept of a context-free grammar cannot be defined without reference to the machine that takes the rules as input and carries out the re-writes. The way the rules are written strongly hint as to the operation of the machine taking them as input. I make some more remarks about this on the back side.