Transcript Formal Languages

Formal Languages: main findings so far
• A problem can be formalised as a formal language
• A formal language can be defined in various ways, e.g.:
• the language accepted by a given DFSA
• the language accepted by a given NDFSA
• the language denoted by a given Regular
Expression
• We stated without proof: DFSA=NDFSA
• We proved: FSA = Regular Expression
• think about what “=“ means
Formal Languages
• FSAs and Regular Expressions are just two methods
for defining a formal language. Many others exist.
• You have seen two equivalence results
• But some methods allow us to define languages that
FSAs (and Regular Expressions) cannot define
• In fact, an entire series of increasingly complex
formal languages is known: the Chomsky hierarchy
• Each requires a more complex type of automaton to
define/accept the language in question.
• At the top of this hierarchy: Turing Machines
Chomsky’s hierarchy
Languages
Automatons
Recursively enumerable =
Turing machine
Context-sensitive =
Context-free
Regular
=
=
LB non-deterministic Turing machine
Non-deterministic pushdown automaton
Finite state automaton
Remainder of the course
• Mechanisms higher up in the hierarchy can recognize
more languages
• Turing Machines resemble FSAs, but are more
powerful. In particular, they
– can write as well as read symbols
– can move left as well as rightward along a string
– have “failure” states as well as “success” states
• We’ll turn to Turing Machines in the third part
of this course
• A full course on formal languages and
computability would tell you about all the
elements of the hierarchy (e.g. context free
languages and pushdown automata)
• The plan of this course is different: we now
turn to a different model of computation
• It is believed that TMs can do anything that
any computer could ever do (Lectures 16-24)
• How can we know what any computer could
ever do?
• Let’s broaden our view by looking at a class of
programming languages entirely different
from JAVA, Pascal, Fortran, Basic, ...
• The name of this programming paradigm: the
functional model of programming
– Mathematical basis: the  calculus
– The programming language: Haskell
• We kill two birds with one stone:
– we get a better view of what programming means
– you learn about an up-and-coming programming
language
– particularly useful for maths