CS计算机代考程序代写 prolog matlab python mips compiler Java Fortran Haskell assembler interpreter FIT2014 Theory of Computation Lecture 1 Introduction

FIT2014 Theory of Computation Lecture 1 Introduction

Monash University
Faculty of Information Technology

FIT2014 Theory of Computation

Lecture 1
Introduction

slides by Graham Farr

COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969

Warning
This material has been reproduced and communicated to you by or on behalf of Monash University in

accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act. Any further reproduction or

communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice. 1 / 25

Lecture overview

I General information

I Languages

I Terminology

I Definitions, Theorems, Proofs

2 / 25

People
Lecturers (Clayton campus)

I Prof. Graham Farr

I Dr Rebecca Robinson

Head Tutor (Clayton)

I Dr Rebecca Robinson

Lecturer (Malaysia campus)

I Assoc. Prof. KokSheik Wong

Tutor (Malaysia)

I Dr Vee Voon Yee

Tutors (Clayton)

I Harald Bögeholz

I Luhan Cheng

I Nathan Companez

I Michael Gill

I Jackson Goerner

I Dr Nhan Bao Ho

I Roger Lim

I Raphael Morris

I Dr Han Duy Phan

I Pooja Pancholi

I Dr Rebecca Robinson

I Grant Sinclair

I Erica Son

I Zhi Hao Tan

I Logan Yip

I Rebecca Young

3 / 25

Textbooks

Recommended Text:

I Michael Sipser, Introduction to the Theory of Computation, PWS Publishing
Company, 2006.

Also useful:

I Daniel I. A. Cohen, Introduction to Computer Theory (2nd Edition), Wiley, New
York, 1997.

For some cultural and historical context, and lots of fun:

I Sydney Padua, The Thrilling Adventures of Lovelace and Babbage, Penguin, 2015.

4 / 25

Classes

Lectures: live-streamed and recorded (see Moodle).

Prac classes (2 hours): start week 1 — this week (Lab 0, on Linux)
Three types:

I Labs 0,1,2: Weeks 1, 4, 10,

I Tutorials (2 hours): Weeks 2, 3, 6, 7, 8, 9, 11, 12

I Interviews: Weeks 5, 13

Timetable: http://www.monash.edu/timetables/allocate/

Mid-Semester Test: week 7

I Tutes/labs continue as usual that week

5 / 25

http://www.monash.edu/timetables/allocate/

Assessment

I Tutorial preparation (5% total)
I all tutorials: weeks 2, 3, 6, 7, 8, 9, 11, 12.
I Each tutorial has a nominated preparation exercise.
I You must make a serious attempt at this question, although it does not need to be

entirely correct.
I Submission deadline:

I on-campus classes: at the start of your tutorial.
I online classes: online by 11:55pm on the Sunday evening just prior to your tutorial

(i.e., at the start of each tutorial week).

I Your attempt will be assessed at the start of each tutorial.
I You get 1 mark for a serious and clear attempt; 0 marks otherwise.
I Maximum 8 marks for the semester.

6 / 25

Assessment (continued)

I Tutorial preparation (5%) (see previous slide)

I Assignment 1 (10%)
I due Friday 11:55pm in week 4
I interviews in week 5
I final mark = provisional mark × interview factor︸︷︷︸

between 0 and 1

I Mid-Semester Test (15%)
I in week 7

I Assignment 2 (20%)
I due Friday 11:55pm in week 10
I interviews sometime in weeks 11–13
I final mark = provisional mark × interview factor︸︷︷︸

between 0 and 1

I Final Exam (50%)

7 / 25

Assessment (continued)

Hurdles

I Total of non-Final-Exam assessments:

two Assignments
+ Mid-Semester Test
+ Tutorial Preparation:

at least 45% of available marks

I Final Exam: at least 45% of available exam marks

I Overall: at least 50%

8 / 25

Assessment (continued)

Academic Integrity

I All assessment in this unit is based on your own individual work. All your
assignments, tests, exams,. . . must be your own work, no-one else’s.

I No plagiarism, collusion, cheating, etc.

I For further details, see:
https://www.monash.edu/students/admin/policies/academic-integrity

I In FIT2014, plagiarism and cheating don’t work.

I Every assignment submission is followed up by an interview to check
understanding and authenticity.

I Any other assessment may be followed up with an interview to check
understanding and authenticity.

9 / 25

https://www.monash.edu/students/admin/policies/academic-integrity

Further information

I Moodle (including Forums → Ed discussion)

I Tutor

I Lecturer

10 / 25

Why study Theory of Computation?

I To understand properly the power and limits of computation;

I To identify whether a problem is tractable or intractable;

I To understand why a particular problem seems hard: is it because of the
limitations of your computer, or because of some intrinsic feature of the problem?

I To be able to identify problems from different fields that have the same underlying
structure.

11 / 25

Some applications

I Pattern recognition (in text, DNA, proteins, financial data, . . . )

I Modelling of natural languages

I Compilers and interpreters for programming languages

I Information security

I Communications: codes, protocols

I Verification of complex systems

12 / 25

Languages

Computation is done with strings of symbols, so . . .

Alphabets

An alphabet is a finite set of symbols.

Its members are called letters or characters.

We often denote it by Σ.

Examples of alphabets:

I {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
I {a, b}
I {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
I {0, 1}

13 / 25

Languages

Words

A word is a finite string of symbols.
A word over alphabet Σ is a finite string of symbols all taken from Σ.
The empty word is the word of length 0, denoted by ε (or sometimes Λ).

Languages

A language over alphabet Σ is a set of words over Σ.

Special languages:
I empty language: ∅ = { }

I not to be confused with the language containing just the empty word : {ε}
I Σk := { all words over Σ of length k }

I E.g.: {a, b}2 = {aa, ab, ba, bb}
I universal language: Σ∗ := { all finite words over Σ }

14 / 25

Languages

Natural languages

I English, Australian, Woiwurrung, Chinese, Auslan, . . . , Hebrew, Indonesian,
Kannada, Hokkien, Croatian, Romanian, Russian, Tamil, Klingon, Spanish,
Turkish, Tagalog, Vietnamese, French, Hungarian, Swedish, Elvish, . . .

Programming languages

I Python, Java, Haskell, awk, C, MIPS Assembler, Smalltalk, Prolog, Simula67,
Interprogram, Algol-60, Cobol, Fortran, . . . , Rust, Java, C++, MATLAB, Racket,
R, Lisp, UwU, Go, . . .

Languages also appear in:

I mathematics, music, knitting, games, . . .

15 / 25

Assumptions and notation

Unless otherwise stated, we use alphabet Σ = {a, b}.

Repetition: a2 = aa, ab3 = abbb, (ab)3 = ababab

If x is a word, then xk is the string obtained by concatenating k copies of x together:

xk = xxx · · · · · · xx︸︷︷︸
k copies of x

(baa)0 = . . .?

16 / 25

Some simple languages

EVEN-EVEN := {all strings in which each of a,b occurs an even number of times}
= {ε, aa, bb, aaaa, aabb, abab, abba, baab, . . .}

Remember, 0 is even!

DOUBLEWORD := {xx : x ∈ Σ∗}
= {all strings obtained by concatenating some string with itself}
= {ε, aa, bb, aaaa, , abab, baba, bbbb, aaaaaa, aabaab, . . .}

Note, εε = ε.

PALINDROMES := {all strings that are the same forwards and backwards}
= {ε, a, b, aa, bb, aaa, aba, bab, bbb, aaaa, , abba, baab, . . .}

17 / 25

Definitions, Theorems, Proofs

Definition

I specifies the precise meaning of something.

Theorem

I a mathematical statement that has been proved to be true.

I has some close but “less significant” relatives: Proposition, Lemma

Proof

I A step-by-step argument that establishes, logically and with certainty, that
something is true.

I Should be verifiable.

18 / 25

Examples of theorems and proofs

Theorem.
English has a palindrome.

Proof. ‘rotator’ is an English word and also a palindrome.

An existential statement . . .

There exists a palindrome in English

. . . just requires one suitable example for a proof.

Most proofs are not this short . . .

19 / 25

Examples of theorems and proofs

Theorem.
Every English word has a vowel or a ‘y’.

Proof.
‘aardvark’ has a vowel.
‘aardwolf’ has a vowel.
‘aasvogel’ has a vowel.
. . .
. . .
‘syzygy’ has a ‘y’.
. . .
‘zygote’ has a vowel.

20 / 25

Theorems and proofs

To prove a universal statement . . .

For every English word, it has a vowel or a ‘y’

. . . you need to cover every possible case.

One way is to go through all possibilities, in turn, and check each one.
But the number of things to check may be huge, or infinite.
So usually we want to reason in a way that can apply to many different
possibilities at once.

21 / 25

Another example theorem

Theorem.
DOUBLEWORD ⊆ EVEN-EVEN

Non-proof:
The examples on the previous slide show that every member of DOUBLEWORD
has an even number of as and an even number of bs.
So every member of DOUBLEWORD is also a member of EVEN-EVEN.

“Proof by example” is not a proof.
. . . except where the Theorem just asserts the existence of a specific example!

22 / 25

Definitions, Theorems, Proofs

Theorem.
DOUBLEWORD ⊆ EVEN-EVEN

To prove a subset relationship, A ⊆ B:
I Prove that every element of A is also

an element of B.
I Start with a general member of A.
I Work towards proving that it also

belongs to B.

I Give names to things.

I Use the definitions of the sets.
Proof. Let w ∈ DOUBLEWORD.
Then w = xx for some word x .
So, # a’s in w = 2 × ( # a’s in x ), so it’s even.
Also, # b’s in w = 2 × ( # b’s in x ), so it’s even too.
So w ∈ EVEN-EVEN.

23 / 25

Related Posts