In the branch logic, we have already dealt with formal languages $L\subset\Sigma^*$ over a given alphabet $\Sigma.$ We learned about the "syntax":https://www.bookofproofs.org/branches/syntax-of-a-formal-language/ and semantics of formal languages. We also learned some important examples of formal languages with particular importance for mathematics - the propositional logic $PL0$ and also the first-order logic $PL1.$
Unlike in the logic branch, we will use the term grammar instead of the term syntax when dealing with formal languages.
This part belonging to the branch theoretical computer science we will deal with formal languages again, but this time from a different perspective - the perspective of programming. Theoretical (and practical) problems occurring in conjunction with formal languages in programming include: * Finding out if an arbitrary string $\omega\in\Sigma^*$ belongs to a given language $L\subset \Sigma^*$ ("How to write a so-called parser for a given programming language?") * Finding out if a language $L\subset \Sigma^*$ with a given "grammar":https://www.bookofproofs.org/branches/syntax-grammar-of-a-formal-language/ has at least one string $\omega in L$? ("Does the grammar allow writing computer programs at all"?) * And if so, is $L$ finite or infinite ("How 'powerful' is a programming language - how many different programs can we write using a given programming language?") * Do two different grammars describe the same language? ("Can we write the same programs using the two different grammars?")
Examples: 1
