Math and science::Theory of Computation

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{aligned} S & \to a S b & (context-free) \\ S & \to A B & (context-free) \\ a A & \to C & (not context-free) \\ b A c & \to B & (not context-free) \\ C A & \to c A & (not context-free) \end{aligned}

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.

22.08.2021