Formal Language Theory

Strings --> Anything that is made entirely of words, alphabets or symbols

Language

A language $L$ is a possibly infinite set of strings over a finite set of alphabets $Σ$ .

Suppose we define two alphabets $a$ and $b$ . The set containing it is $Σ$ .

Σ = {a, b}

$Σ^{*}$ is an infinite set of all finite strings that you can make from $Σ$ .

Σ^{*} = {a, b, a b, b a, a a, b b, \overset{string}{\overset{⏞}{a a b}}, b a b a \dots} = {w | w begins with a}

Language $L$ is a set, whose elements follow specific rules that uses strings from $Σ^{*}$ . For example, a Language that encode any sequence of $a$ or $b$ that starts with an $a$ can be expressed as.

L = {a, a b, a a b, a a a \dots}

All languages are a subset of $Σ^{*}$ .

L \subseteq Σ^{*}

And the set of all possible languages over $Σ$ is the power of $Σ$ , or $P (Σ^{*})$ . The power set of a set is the set of all possible subsets of that set, including the empty set and the set itself.

P (Σ^{*}) = {{a, b}, {a, b, a b} \dots} = {L_{1}, L_{2}, L_{3} \dots}

The cardinality or size of the set (number of elements) is

| P (Σ^{*}) | = 2^{| Σ^{*} |}

where $| P (Σ^{*}) |$ is the number of possible languages given $Σ$ . (Its prob $ℵ_{0}$ )

Grammar

A logical system that can be used to prove that a given string $u$ is a member of $L$ .

In a grammar, $R$ is a finite set of rules of the form $ψ \to ω$ , where $ψ$ and $ω$ are strings, which can be used to derive the strings in a given language.

Atomic Propositions

In propositional logic, atomic propositions are the simplest statements that cannot be broken down into smaller parts. For example, $p = “It is raining”, q = “It is cold”$ . These atomic propositions represent basic declarative statements that are either true or false. They are the fundamental building blocks of logical formulas.

Terminal and Non-terminal Symbols in Formal Grammars

In formal language theory, a grammar consists of:

Terminal symbols: These are the basic symbols (e.g., words or characters) that appear in the strings generated by the grammar. Terminal symbols cannot be replaced or rewritten further.
Non-terminal symbols: These are placeholders or variables that can be replaced by strings of terminals and/or other non-terminals according to production rules.

A production rule has the form:

A \to α

where, $A$ is a non-terminal symbol, and $α$ is a string consisting of terminals and/or non-terminals that can replace $A$ . For example, in English, non terminals can be like $N \sim noun$ , or $V \sim verb$

$N \to “cat”$
$V \to "run"$
then the non-terminal noun $N$ can be replaced by the terminal symbol "cat".

So if the sentence $S$ is $S \to N V$ . Then, we replace $N$ with cat, and $V$ with run. To get the sentence cat run. Thus we can say that $S \to N V \in R$ .

A grammar can be expressed in a tuple with 4 elements

(V, Σ, R, S)

where $V$ is the set of non-terminal symbols like ${N, V}$ , $Σ$ is the set of terminal symbols like ${cat, run}$ . $R$ is a set of rules ${S \to N V}$ . And $S$ is the start symbol.