We want to recap the concepts of a grammar and a formal language in the following definition.
Let $\Sigma$ be an alphabet and $G=(V,T,R,S)$ be a grammar over this alphabet. We say a string $y\in\Sigma^*$ can be syntactically derived from another string $x$ using the grammar $G$ (denoted by $x\Rightarrow y$), if $$\exists u,w\in (V\cup T)^*, \exists P\to C\in R: (x=uPv\wedge y=uCv).$$
In other words, $x\Rightarrow y$ if and only the two strings have the form $x=uPw$ and $y=uCw$ (for some other strings $u,w$) and there is a rule $P\to C.$
Note that $y$ can be derived from $x$ by applying several rules, e.g. $x\Rightarrow z_1\Rightarrow\cdots\Rightarrow z_n\Rightarrow y$. It is, therefore, reasonable to require that the set $R$ of grammar rules is a transitive relation. Denoting by $\Rightarrow^*$ the transitive hull of the grammar rule relation $R,$ we can now state that a language $L\subset\Sigma^*$ is said to be generated by the grammar $G$ if and only if
$$L=L(G)=\{y\in\Sigma^*\mid S\Rightarrow^* y\}.$$
In this case, we call $L$ a formal language.
Applications: 1
Branches: 2
Chapters: 3 4 5 6 7
Definitions: 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Explanations: 31
Proofs: 32
