Formal Languages
Sets of sequences of symbols
- Specification
- We want to specify it precisely enough for us to create proofs
- We can prove if a sequence of symbols is a valid program
- We can prove that there exists a solution for a problem
- We want to specify it precisely enough for us to create proofs
- Recognition (algorithm)
- From the specification, automatically generate an algorithm
- Recognize whether a particular sequence is in the set and making an algorithm to do so
- Some languages can't automatically do this
- Formally, given word
, is
- From the specification, automatically generate an algorithm
- Interpretation/translation
- Build data structure
- Tell us about the structure about a program
- Build data structure
Alphabet
Definition
An alphabet (
Examples
Word
Definition
A word over
Examples
01101(5 symbols)42(2 symbols)def var(2 symbols)- The "empty word"
(0 symbols)
Language
Definition
A language is a set of words (can be infinite)
Examples
- All strings of 32 bits (finite)
- All prime numbers written in decimal (infinite)
- All valid Lacs programs
- All correct solutions to assignment 6
empty language the language containing the empty word
Language Class
Definition
A language class is a set of languages
Example
-
Finite languages
-
Regular languages
-
Context-free languages
-
Decidable languages
- There exists an algorithm to decide if a word exists in the language or not
-
Undecidable languages
All finite languages are regular, all regular languages are context-free, and all context-free languages are decidable, i.e