Formal Languages

Learning Objectives Define the core components of a formal language: alphabet, string, language, and grammar. Differentiate between a formal language and a natural language (e.g., English). Interpret and apply basic regular expression operators (*, +, |) to match strings. Construct a simple regular expression for a given language pattern. Generate a valid string by applying the production rules of a given formal grammar. Determine if a given string is a member of a language defined by a simple grammar or regular expression. How does your code compiler know that `int x = 5;` is valid but `5 = x int;` is nonsense? 🤔 It's all thanks to a set of strict, mathematical rules! This lesson introduces Formal Languages, the precise, unambiguous languages that form the bedrock of...

TermDefinitionExample Alphabet (Σ)A finite, non-empty set of symbols. An alphabet is the collection of all allowed characters.The binary alphabet is Σ = {0, 1}. The lowercase English alphabet is Σ = {a, b, c, ..., z}. String (or Word)A finite sequence of symbols chosen from a particular alphabet. The empty string, denoted by ε (epsilon), is a string with zero symbols.Over the alphabet Σ = {0, 1}, strings include "0110", "1", "000", and the empty string ε. Language (L)A set of strings over a particular alphabet. A language can be finite or infinite.Let Σ = {a, b}. A language L could be the set of all strings that start with 'a': L = {"a", "aa", "ab", "aab", "aba", ...}. Formal Grammar (G)A set of prod...

Regular Expression Operators Operators: * (Kleene Star), + (Kleene Plus), | (Alternation/OR), () (Grouping) These operators are used to build complex patterns from simple characters. `a*` means zero or more 'a's. `a+` means one or more 'a's. `a|b` means 'a' or 'b'. `(ab)+` means one or more sequences of "ab". Grammar Production Rules Format: `A -> β` (read as 'A produces β' or 'A can be replaced by β') This is the core of a formal grammar. `A` must be a single non-terminal symbol. `β` is a string of terminals and/or non-terminals. To generate a string, you start with the designated 'start symbol' and repeatedly apply these rules until only terminal symbols remain.