Course Overview
• Why this course “formal languages and automata theory?”
• What do computers really do?
• What are the practical benefits/application of formal languages and
automata theory?
– Will you ever be using these facts / skill?
1
What do computers really do?
– Take an input, process, and produce correct output.
• What is input? In abstract way?
• A finite string. On a finite alphabet – a set of characters.
• Output?
• “Input processed successfully,” Or “not”.
• In other words: True / False.
• Everything else in output is just the “detail”!
• Don’t forget the “finite time” for processing! Definition of algorithm.
2
Practical aspects of Formal Lang. Auto. Theory?
• Difference between a “programmer” and a “computer scientist”
• Software system design.
• Many hardware design.
• Actual algorithms, e.g. string processing.
• And of course, new language and compiler design.
• Anything else?
3
Formal Language
• Finite set of alphabets Σ:
e.g., {0, 1}, {a, b, c}, { ‘{‘, ‘}’ }
• Language L is a subset of strings on Σ,
• e.g., {00, 110, 01} a finite language,
• or, {strings starting with 0} an infinite language
• Σ* is a special language with all possible strings on Σ
4
Finite State Machine
……..
0 1 1 0 0
Finite
Control
• Tape, broken into cells
• Tape head.
• Finite control, i.e., a program, containing the position of the read head,
current symbol being scanned, and the current “state”, etc.
• A string is placed on the tape, read head is positioned at the left end, and
the machine reads the string one symbol at a time until all symbols have
been read,
• and then either accepts or rejects the input (to be in the language or not)
5
Hierarchy of languages
Non-Recursively Enumerable Languages
Recursively Enumerable Languages
Recursive Languages
Context-Free Languages
Regular Languages
6
General Topics
• Abstract machine models of computation (e.g., Deterministic Finite Automata,
Non-deterministic FA, Turing Machine)
• Classes of grammars (e.g., regular grammars, context-free grammars, context
sensitive grammars, unrestricted grammars)
• Classes of formal languages (e.g., regular, context-free, context-sensitive,
recursive, recursively enumerable)
– formal languages evolve to programming languages, and related to natural
languages
• Limitation of computational power of the abstract machine models
– not about speed in this class, but about ultimate computability
• Relationships between the languages, grammars and machines.
7
Language: Definitions
• Symbol – An atomic unit, such as a digit, character, lower-case letter, etc.
Sometimes a word. [Formal language does not deal with the “meaning” of
the symbols.]
• Alphabet – A finite set of symbols, usually denoted by Σ.
Σ = {0, 1} Σ = {0, a, , 4} Σ = {a, b, c, d}
• String – A finite length sequence of symbols, presumably from some alphabet.
u=ε w = 0110 y = 0aa x = aabcaa z = 111
special string: ε (also denoted by λ)
concatenation: wz = 0110111
length: |w| = 4 |x| = 6 but |u| = 0
reversal: yR = aa0
8
• Some special sets of strings:
Σ* All strings of symbols from Σ
Σ+ Σ* - {ε}
• Example:
Σ = {0, 1}
Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001,…}
Σ+ = {0, 1, 00, 01, 10, 11, 000, 001,…}
• A (formal) language is:
1) A set of strings from some alphabet (finite or infinite), in other words…
2) any subset L of Σ*
• Some special languages:
{} The empty set/language, containing no strings
{ε} A language containing one string, the empty string.
9
• Examples:
Σ = {0, 1}
L = {x | x is
in Σ* and x contains an even number of 0’s}
Σ = {0, 1, 2,…, 9, .}
L = {x | x is in Σ* and x forms a finite length real number}
= {0, 1.5, 9.326,…}
Σ = {a, b, c,…, z, A, B,…, Z}
L = {x | x is in Σ* and x is a Pascal reserved word}
= {BEGIN, END, IF,…}
Σ = {Pascal reserved words} U { (, ), ., :, ;,…} U {Legal Pascal identifiers}
L = {x | x is in Σ* and x is a syntactically correct Pascal program}
Σ = {English words}
L = {x | x Σ* and x is a syntactically correct English sentence}
10