Formal Languages and Logic/Chomsky grammars

Definition (Chomsky grammar):

A Chomsky grammar is a quartuple $G=(\Sigma ,N,P,S)$, where $\Sigma$ is an alphabet, $N$ is a set such that $\Sigma \cap N=\emptyset$, $P\subseteq (\Sigma \cup N)^{*}\times (\Sigma \cup N)^{*}$ and $S\in N$.

Definition (terminal symbol):

Let $G=(\Sigma ,N,P,S)$ be a Chomsky grammar. A nonterminal symbol of $G$ is an element of $\Sigma$.

Definition (nonterminal symbol):

Let $G=(\Sigma ,N,P,S)$ be a Chomsky grammar. A nonterminal symbol of $G$ is an element of $N$.

Definition (production):

Let $G=(\Sigma ,N,P,S)$ be a Chomsky grammar. A production of $G$ is an element of $P$.

Productions will be denoted as $\alpha \to \beta$ instead of the tuple notation $(\alpha ,\beta )$.

Definition (start symbol):

Let $G=(\Sigma ,N,P,S)$ be a Chomsky grammar. Then $S$ is the start symbol of $G$.

Definition (language generated by a Chomsky grammar):

Let $G=(\Sigma ,N,P,S)$ be a Chomsky grammar. Then the language generated by $G$ is the language

$\{w\in \Sigma ^{*}|\}$