\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Answer
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
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.