This repository contains basic notes about Theoretical-Computer-Science course of Università Della Calabria. You can use this repo for review but not for study as proofs of the theorems are missing. If you like share and star the repository :)
What is a language? It is simple. A set of strings. Now the question is obvious. What are strings? Strings are a sequence of simbol of an alphabet. Mathematically we denote with this simbol
Now we can define formally a language given an alphabet
Example:
Grammars generate languages. Formally a grammar is a quadruple
- V is the set of non-terminal symbols
- T is the set of terminal symbols
- S is the initial non-terminal symbol
- P is a set of productions
What is a production? Simple a rule that allows you to replace the left side with the right.
Formally a production is
We can divide grammars in 4 types base on the language they generate:
- Type 3 grammar: grammar production are of the type,
$A => a$ $A \in V,\ a \in T $ $A => Ba, A,B \in V, a \in T$ $A => aB, A,B \in V, a \in T$ - Type 2 grammar: grammar production are of the type,
$A => \Gamma $ $A \in V, \Gamma \in (V \cup T)^*$ - Type 0 grammar: grammar production are of the type,
$\alpha A \beta => \alpha \gamma \beta$ $A \in V$ ,$\alpha , \gamma , \beta \in (V \cup T )^*$
Chomsky_hierarchy
Type 3 languages are generated by regular expression and recognized by Deterministic finite state automata DFA
Regular_language
Deterministic finite state automata DFA formally is a
- Q is the set of states of the finite state automaton.
-
$\Sigma$ is the alphabeth. -
$q_{0}$ is the initial state of the DFA. -
$F \subseteq Q$ is the set of final states of automata. -
$\delta$ is the set of transactions. In a DFA the transactions are of the type:$Q \times \Sigma \rightarrow Q $
Deterministic_finite_automaton