The Central Idea
A formal language is a set of strings built from a specified alphabet.
If
\[ \Sigma=\{0,1\}, \]then a language might contain all binary strings ending in \(1\):
\[ L=\{1,01,11,001,101,111,\ldots\}. \]The defining feature is not what the symbols mean in ordinary life, but the structural rule determining which strings belong to the set.
Alphabet
An alphabet is a finite set of symbols.
It is usually written
\[ \Sigma. \]Examples include
\[ \Sigma=\{0,1\}, \] \[ \Sigma=\{a,b,c\}, \]or a larger collection of symbols used by a particular formal system.
Symbols Are Atomic within the Alphabet
At the level of the formal language, symbols are treated as indivisible units.
If
\[ \Sigma=\{a,b\}, \]then \(a\) and \(b\) are the basic symbols from which strings are formed.
Strings
A string is a finite sequence of symbols from an alphabet.
If
\[ \Sigma=\{a,b\}, \]examples include
\[ a,\qquad b,\qquad ab,\qquad baa,\qquad abbab. \]String Length
The length of a string \(w\) is written
\[ |w|. \]For example, if
\[ w=abba, \]then
\[ \boxed{|w|=4}. \]The Empty String
The string containing no symbols is called the empty string.
It is written
\[ \varepsilon. \]Its length is
\[ \boxed{|\varepsilon|=0}. \]The Empty String Is Not the Empty Set
The empty string
\[ \varepsilon \]is a string of length zero.
The empty set
\[ \varnothing \]contains no elements.
Therefore,
\[ \boxed{\varepsilon\ne\varnothing}. \]Concatenation
The concatenation of two strings places the second string immediately after the first.
If
\[ x=ab \]and
\[ y=baa, \]then
\[ \boxed{xy=abbaa}. \]Concatenation Is Ordered
In general,
\[ xy\ne yx. \]For example,
\[ ab\cdot ba=abba, \]while
\[ ba\cdot ab=baab. \]String concatenation is therefore not generally commutative.
The Empty String as an Identity
Concatenating the empty string changes nothing:
\[ \boxed{\varepsilon w=w\varepsilon=w}. \]Thus \(\varepsilon\) is the identity element for string concatenation.
Concatenation and Length
String lengths add under concatenation:
\[ \boxed{|xy|=|x|+|y|}. \]If \(|x|=3\) and \(|y|=5\), then
\[ |xy|=8. \]Powers of a String
Repeated concatenation of a string is written using powers.
For example,
\[ w^2=ww, \] \[ w^3=www. \]By convention,
\[ \boxed{w^0=\varepsilon}. \]Example of String Powers
Let
\[ w=ab. \]Then
\[ w^2=abab, \] \[ w^3=ababab, \]and
\[ w^0=\varepsilon. \]Powers of an Alphabet
The notation
\[ \Sigma^n \]denotes the set of all strings of length exactly \(n\) over \(\Sigma\).
If
\[ \Sigma=\{0,1\}, \]then
\[ \Sigma^2=\{00,01,10,11\}. \]How Many Strings Are in \(\Sigma^n\)?
If
\[ |\Sigma|=k, \]then every one of the \(n\) positions has \(k\) choices.
Therefore,
\[ \boxed{|\Sigma^n|=k^n}. \]Kleene Star
The Kleene star of an alphabet is
\[ \Sigma^* = \bigcup_{n=0}^{\infty}\Sigma^n. \]It contains every finite string over \(\Sigma\), including the empty string.
Example of Kleene Star
If
\[ \Sigma=\{a,b\}, \]then
\[ \Sigma^* = \{\varepsilon,a,b,aa,ab,ba,bb,aaa,\ldots\}. \]The set is infinite even though the alphabet itself is finite.
Kleene Plus
The notation
\[ \Sigma^+ \]denotes all nonempty finite strings over \(\Sigma\).
Thus,
\[ \boxed{\Sigma^+=\Sigma^*\setminus\{\varepsilon\}}. \]Formal Language
A language over \(\Sigma\) is any subset of \(\Sigma^*\):
\[ \boxed{L\subseteq\Sigma^*}. \]A language may be:
- finite;
- infinite;
- empty;
- equal to all of \(\Sigma^*\).
Finite Language Example
Let
\[ \Sigma=\{a,b\}. \]Then
\[ L=\{a,ab,bba\} \]is a finite language over \(\Sigma\).
Infinite Language Example
Consider
\[ L=\{a^n:n\ge0\}. \]Then
\[ L=\{\varepsilon,a,aa,aaa,\ldots\}. \]This language contains infinitely many strings.
Set-Builder Description of a Language
Languages are often described using set-builder notation.
For binary strings ending in \(1\),
\[ \boxed{ L=\{w\in\{0,1\}^*:w\text{ ends in }1\} }. \]This separates the universe of possible strings from the membership condition.
Membership
If a string \(w\) belongs to language \(L\), write
\[ w\in L. \]If it does not belong,
\[ w\notin L. \]Union of Languages
The union
\[ L_1\cup L_2 \]contains every string belonging to at least one of the two languages.
This is the set-theoretic OR of the languages.
Intersection of Languages
The intersection
\[ L_1\cap L_2 \]contains exactly the strings belonging to both languages.
This is the set-theoretic AND of the language conditions.
Difference of Languages
The difference
\[ L_1\setminus L_2 \]contains strings in \(L_1\) that are not in \(L_2\).
Complement of a Language
The complement of \(L\) depends on the chosen alphabet.
Relative to \(\Sigma^*\),
\[ \boxed{ \overline{L} = \Sigma^*\setminus L }. \]The ambient set \(\Sigma^*\) must therefore be understood.
Concatenation of Languages
If \(L_1\) and \(L_2\) are languages, then
\[ L_1L_2 = \{xy:x\in L_1,\ y\in L_2\}. \]Every string in the product is formed by concatenating one string from \(L_1\) with one from \(L_2\).
Example of Language Concatenation
Let
\[ L_1=\{a,b\} \]and
\[ L_2=\{0,1\}. \]Then
\[ \boxed{ L_1L_2=\{a0,a1,b0,b1\} }. \]Language Concatenation Is Not Generally Commutative
In general,
\[ L_1L_2\ne L_2L_1. \]For the previous example,
\[ L_2L_1=\{0a,0b,1a,1b\}, \]which differs from \(L_1L_2\).
Powers of a Language
Define
\[ L^2=LL, \] \[ L^3=LLL, \]and, by convention,
\[ \boxed{L^0=\{\varepsilon\}}. \]Kleene Star of a Language
The Kleene star of a language is
\[ \boxed{ L^* = \bigcup_{n=0}^{\infty}L^n }. \]It contains all strings formed by concatenating zero or more strings from \(L\).
Example of Language Star
Let
\[ L=\{ab\}. \]Then
\[ L^* = \{\varepsilon,ab,abab,ababab,\ldots\}. \]Regular Expressions
A regular expression is a symbolic notation for describing regular languages.
Its basic operations correspond to:
- choice or union;
- concatenation;
- repetition through Kleene star.
Basic Regular Expressions
Over alphabet \(\Sigma\), basic regular expressions include:
- \(\varnothing\), representing the empty language;
- \(\varepsilon\), representing the language \(\{\varepsilon\}\);
- each symbol \(a\in\Sigma\), representing the language \(\{a\}\).
Regular-Expression Union
If expressions \(R\) and \(S\) describe languages \(L(R)\) and \(L(S)\), then a union expression describes
\[ L(R)\cup L(S). \]Depending on notation, this operation may be written with a vertical bar, plus sign, or another union-style symbol.
Regular-Expression Concatenation
Placing two regular expressions next to each other represents language concatenation.
If \(R\) describes strings from \(L_1\) and \(S\) describes strings from \(L_2\), then
\[ RS \]describes
\[ L_1L_2. \]Regular-Expression Star
If \(R\) describes language \(L\), then
\[ R^* \]describes
\[ L^*. \]This means zero or more repetitions of strings described by \(R\).
Example: Binary Strings Ending in 1
Over
\[ \Sigma=\{0,1\}, \]a regular expression for strings ending in \(1\) is
\[ \boxed{(0\mid1)^*1}. \]The prefix may be any binary string, but the final symbol must be \(1\).
Example: Strings Containing 01
A regular expression for binary strings containing \(01\) somewhere is
\[ \boxed{(0\mid1)^*01(0\mid1)^*}. \]The first star allows any prefix.
The middle \(01\) forces the desired substring.
The final star allows any suffix.
Regular Expressions and Finite Automata
Regular expressions and finite automata describe exactly the same class of languages.
A language is regular if and only if it can be:
- recognized by a finite automaton;
- described by a regular expression.
Why Equivalent Descriptions Matter
A state machine may make operational behavior easy to see.
A regular expression may make a string pattern easy to write compactly.
Switching between equivalent representations is a central technique in formal language theory.
Grammar
A grammar is a finite system of production rules used to generate strings.
A common formal description is
\[ \boxed{G=(V,\Sigma,P,S)}. \]Here:
- \(V\) is a set of variables or nonterminal symbols;
- \(\Sigma\) is the terminal alphabet;
- \(P\) is a set of production rules;
- \(S\) is the start symbol.
Terminals and Nonterminals
Terminal symbols appear in completed strings of the language.
Nonterminal symbols are temporary symbols used during generation.
A derivation repeatedly replaces nonterminals according to production rules.
Production Rules
A production rule specifies an allowed replacement.
For example,
\[ S\to aS \]means that \(S\) may be replaced by \(aS\).
Another rule such as
\[ S\to\varepsilon \]allows the derivation to terminate.
Example Grammar
Consider
\[ S\to aS \]and
\[ S\to\varepsilon. \]Starting from \(S\), we can derive
\[ S\Rightarrow aS \Rightarrow aaS \Rightarrow aaaS \Rightarrow aaa. \]This grammar generates
\[ \boxed{\{a^n:n\ge0\}}. \]Derivation
A derivation is a sequence of valid production-rule applications.
The symbol
\[ \Rightarrow \]is commonly used for one derivation step.
Repeated derivation may be written
\[ \Rightarrow^*. \]Generated Language
The language generated by grammar \(G\) is written
\[ L(G). \]It consists of all terminal strings that can be derived from the start symbol.
Recognition versus Generation
Automata are usually described as recognizing strings.
Grammars are usually described as generating strings.
Both approaches define languages, but from different directions.
A Simple Regular Grammar
Consider
\[ S\to 0S \] \[ S\to 1S \] \[ S\to 1. \]This grammar generates nonempty binary strings ending in \(1\).
It therefore describes a regular language.
Syntax
Syntax concerns which strings are structurally well formed according to a formal system.
Formal languages provide precise syntactic rules independent of informal interpretation.
Semantics
Semantics concerns the meaning assigned to well-formed strings.
A formal language can be studied purely syntactically, even before any external meaning is attached to its strings.
Syntax and Semantics Are Different
A string may be syntactically valid yet semantically meaningless in a particular application.
Conversely, an intended idea may fail to be representable if the formal syntax does not permit the required string.
Formal systems keep these issues separate.
Parsing
Parsing analyzes how a string fits the structural rules of a language or grammar.
In programming languages, parsing determines whether tokens can be combined according to the language grammar.
Formal Languages in Programming
Programming languages rely on formal-language ideas at several levels:
- characters form tokens;
- tokens form expressions and statements;
- grammars define valid program structure;
- parsers analyze that structure.
Formal Languages in Search
Pattern-matching systems often use regular expressions to describe allowable text patterns.
Finite automata can then implement recognition of those patterns.
Formal Languages in Communication
Communication protocols define which sequences of messages or symbols are permitted.
Formal-language tools can describe those allowed sequences precisely.
Formal Languages in Mathematics
Mathematical notation itself can be viewed as a formal symbolic language.
Expressions are built from approved symbols according to structural rules, and those expressions are then given mathematical meaning.
Common Error: Confusing an Alphabet with a Language
An alphabet contains symbols.
A language contains strings built from those symbols.
Thus,
\[ \Sigma=\{0,1\} \]is not the same object as
\[ L=\{0,01,111\}. \]Common Error: Confusing \(\varepsilon\) with \(\varnothing\)
The empty string is one string:
\[ \{\varepsilon\} \]contains one element.
The empty language
\[ \varnothing \]contains zero strings.
Common Error: Forgetting \(\varepsilon\) in Kleene Star
Since zero repetitions are allowed,
\[ \boxed{\varepsilon\in L^*} \]for every language \(L\).
Common Error: Assuming Concatenation Is Commutative
In general,
\[ xy\ne yx \]and
\[ L_1L_2\ne L_2L_1. \]Order matters.
Common Error: Confusing Union with Concatenation
The union
\[ L_1\cup L_2 \]selects strings belonging to either language.
The concatenation
\[ L_1L_2 \]builds new strings by joining one string from each language.
Common Error: Ignoring the Ambient Alphabet
Language complement depends on \(\Sigma^*\).
Without knowing the alphabet, the complement may be ambiguous.
Common Error: Treating a Regular Expression as an Ordinary String
A regular expression is a description of a set of strings.
It is not usually itself one of the strings being described.
A Reliable Procedure for Working with Strings
- Identify the alphabet.
- Check that every symbol belongs to the alphabet.
- Determine the string length if needed.
- Apply concatenation in the stated order.
- Remember that \(\varepsilon\) contributes length zero.
A Reliable Procedure for Describing a Language
- Specify the alphabet \(\Sigma\).
- Identify the universe \(\Sigma^*\).
- State the membership condition precisely.
- Give several strings that belong to the language.
- Give several strings that do not belong when useful.
- Check whether \(\varepsilon\) should be included.
A Reliable Procedure for Reading a Regular Expression
- Identify the smallest symbol-level components.
- Interpret concatenation as sequence.
- Interpret union as alternatives.
- Interpret star as zero or more repetitions.
- Use parentheses to determine grouping.
- Describe the resulting language in words.
A Reliable Procedure for Reading a Grammar
- Identify the start symbol.
- Separate terminals from nonterminals.
- List the production rules.
- Apply one production at a time.
- Continue until only terminal symbols remain.
- Inspect several derivations to infer the language pattern.
Example: Full Language Description Workflow
Let
\[ \Sigma=\{0,1\}. \]Define
\[ L=\{w\in\Sigma^*:w\text{ contains exactly one }1\}. \]Examples in the language include
\[ 1,\qquad 10,\qquad 01,\qquad 00100. \]Examples not in the language include
\[ \varepsilon,\qquad 000,\qquad 11,\qquad 101. \]A compact regular expression is
\[ \boxed{0^*10^*}. \]Practice 1: Alphabet and String
Let
\[ \Sigma=\{a,b\}. \]Is \(abba\) a string over \(\Sigma\)?
Practice 2: String Length
Find
\[ |101001|. \]Practice 3: Concatenation
If
\[ x=ab \]and
\[ y=ba, \]find \(xy\).
Practice 4: Alphabet Power
If
\[ \Sigma=\{0,1\}, \]list \(\Sigma^2\).
Practice 5: Count Strings
An alphabet contains \(3\) symbols.
How many strings of length \(4\) can be formed?
Practice 6: Kleene Star
Is
\[ \varepsilon \]always an element of \(\Sigma^*\)?
Practice 7: Language Concatenation
Let
\[ L_1=\{a,b\} \]and
\[ L_2=\{0\}. \]Find \(L_1L_2\).
Practice 8: Regular Expression
What language over \(\{0,1\}\) is described by
\[ (0\mid1)^*0? \]Practice 9: Grammar
Consider
\[ S\to aS \] \[ S\to b. \]Give three strings generated by this grammar.
Practice 10: Recognition versus Generation
Which is more naturally described as recognizing a language: an automaton or a grammar?
Practice Answers
Practice 1
Yes. Every symbol in \(abba\) belongs to
\[ \Sigma=\{a,b\}. \]Practice 2
\[ \boxed{|101001|=6}. \]Practice 3
\[ \boxed{xy=abba}. \]Practice 4
\[ \boxed{\Sigma^2=\{00,01,10,11\}}. \]Practice 5
\[ 3^4=81. \]Therefore,
\[ \boxed{81}. \]Practice 6
Yes.
Because \(\Sigma^*\) includes \(\Sigma^0\),
\[ \boxed{\varepsilon\in\Sigma^*}. \]Practice 7
\[ \boxed{L_1L_2=\{a0,b0\}}. \]Practice 8
It describes all binary strings ending in \(0\).
Practice 9
Examples include
\[ b,\qquad ab,\qquad aab. \]In general, the grammar generates
\[ \{a^nb:n\ge0\}. \]Practice 10
An
\[ \boxed{\text{automaton}} \]is naturally described as recognizing a language, while a grammar is naturally described as generating one.
What to Remember
- An alphabet is a finite set of symbols.
- A string is a finite sequence of symbols from an alphabet.
- The empty string is \(\varepsilon\), and \(|\varepsilon|=0\).
- Concatenation joins strings in order and is not generally commutative.
- \(\Sigma^n\) contains strings of length \(n\), while \(\Sigma^*\) contains all finite strings.
- A formal language is any subset of \(\Sigma^*\).
- Languages can be combined with union, intersection, difference, complement, concatenation, and star.
- Regular expressions describe regular languages.
- Grammars generate strings through production rules.
- Automata recognize languages, while grammars provide a complementary generative viewpoint.
The central habit is to keep symbols, strings, languages, and descriptions of languages clearly separated as different mathematical objects.
Where We Go Next
Formal languages give us precise sets of symbolic strings and systematic ways to describe them. The next lesson turns back to logical formulas and asks whether a collection of constraints can all be made true at the same time.
The next lesson, Satisfiability and Constraint Systems, introduces satisfying assignments, CNF constraints, SAT-style reasoning, and finite logical solution spaces.