# Grammars

## Introduction

A grammar is inyutively a set of rules which are used to construct a language contained in ${\Sigma }^{*}$, for some alphabet $\Sigma$. These rules allow us to replace symbols or strings of symbols with other symbols or strings until we finally have strings of symbols contained in $\Sigma$ allowing us to form an element of the language.

By placing restrictions on the rules, we shall see that can develop different types of languages. In particular we can restrict our rules to produce desirable qualities in our langauge.

## Definition 4.1

A formal grammar, or phrase structure grammar $\Gamma$.denoted by the 4-tuple $\left(N,\Sigma ,S,P\right)$ which consists of a finite set of nonterminal symbols $N$, a finite set of terminal symbols $\Sigma$, an element $S\in R$ called the start symbol and a finite set of productions $P$, which is a relation in $\left(N\cup \Sigma {\right)}^{*}$ such that each first element is an ordered pair of $P$ contains a symbol from $N$ and at least one production $S$ as the left string in some ordered pair.