Difference between revisions of "BSc: Theoretical Computer Science"

From IU
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
  +
 
= Theoretical Computer Science =
  
= Theoretical Computer Science =
  +
* '''Course name''': Theoretical Computer Science
  +
* '''Code discipline''': BS-
  +
* '''Subject area''':
   
  +
== Short Description ==
−
* <span>'''Course name:'''</span> Theoretical Computer Science
  
  +
This course covers the following concepts: Automata Theory; Formal Grammars; Computability.
−
* <span>'''Course number:'''</span> BS-
  
   
−
== Course characteristics ==
 +
== Prerequisites ==
   
−
=== Key concepts of the class ===
 +
=== Prerequisite subjects ===
  +
* CSE113 Logic and Discrete Mathematics: set theory, inductive definitions and proofs, predicate logic, proof techniques (for example by contradiction, diagonalization...), algebraic structures (preferably).
   
  +
=== Prerequisite topics ===
−
* Automata Theory
  
−
* Formal Grammars
  
−
* Computability
  
   
−
=== What is the purpose of this course? ===
  
   
  +
== Course Topics ==
  +
{| class="wikitable"
  +
|+ Course Sections and Topics
  +
|-
  +
! Section !! Topics within the section
  +
|-
  +
| Automata Theory ||
  +
# Languages
  +
# Finite State Automata
  +
# Pushdown Automata
  +
# Nondeterminism
  +
# Turing Machines
  +
|-
  +
| Formal Grammars ||
  +
# Chomsky Hierarchy
  +
# Regular Expressions
  +
# Relationships with Automata
  +
|-
  +
| Computability ||
  +
# Undecidability
  +
# Halting Problem
  +
# Rice Theorem
  +
|}
  +
== Intended Learning Outcomes (ILOs) ==
  +
  +
=== What is the main purpose of this course? ===
 
A good software developer ignorant of how the mechanics of a compiler works is not better than a good pilot when it comes to fix the engine and he will definitively not be able to provide more than average solutions to the problems he is employed to solve. Like automotive engineering teach us, races can only be won by the right synergy of a good driving style and mechanics. Most importantly, limits of computation cannot be ignored in the same way we precisely know how accelerations, forces and frictions prevent us from racing at an unlimited speed. This course will investigate the prerequisites to understand compilers functioning. Although the act of compilation appears deceptively simple to most of the modern developers, great minds and results are behind the major achievements that made this possible. All starts with the Epimenides paradox (about 600 BC), which emphasizes a problem of self-reference in logic and brings us to the short time window between WWI and WW2 when, in 1936, Alan Turing proved that a general procedure to identify algorithm termination simply does not exist. Another major milestone has been reached by Noam Chomsky in 1956 with his description of a hierarchy of grammars. In this long historical timeframe we can put most of the bricks with which we build modern compilers. The course will be an historical tour through the lives of some of the greatest minds who ever lived on this planet.
  
A good software developer ignorant of how the mechanics of a compiler works is not better than a good pilot when it comes to fix the engine and he will definitively not be able to provide more than average solutions to the problems he is employed to solve. Like automotive engineering teach us, races can only be won by the right synergy of a good driving style and mechanics. Most importantly, limits of computation cannot be ignored in the same way we precisely know how accelerations, forces and frictions prevent us from racing at an unlimited speed. This course will investigate the prerequisites to understand compilers functioning. Although the act of compilation appears deceptively simple to most of the modern developers, great minds and results are behind the major achievements that made this possible. All starts with the Epimenides paradox (about 600 BC), which emphasizes a problem of self-reference in logic and brings us to the short time window between WWI and WW2 when, in 1936, Alan Turing proved that a general procedure to identify algorithm termination simply does not exist. Another major milestone has been reached by Noam Chomsky in 1956 with his description of a hierarchy of grammars. In this long historical timeframe we can put most of the bricks with which we build modern compilers. The course will be an historical tour through the lives of some of the greatest minds who ever lived on this planet.
   
  +
=== ILOs defined at three levels ===
−
== Prerequisites ==
  
−  
−
[https://eduwiki.innopolis.university/index.php/BSc:Logic_and_Discrete_Mathematics CSE113 Logic and Discrete Mathematics]: set theory, inductive definitions and proofs, predicate logic, proof techniques (for example by contradiction, diagonalization...), algebraic structures (preferably).
  
−  
−  
−
== Course Objectives Based on Bloom’s Taxonomy ==
  
−  
−
=== What should a student remember at the end of the course? ===
  
−  
−
By the end of the course, the students should be able to recognize and define
  
   
  +
==== Level 1: What concepts should a student know/remember/explain? ====
  +
By the end of the course, the students should be able to ...
 
* Define a formal language
  
* Define a formal language
 
* List different computational models
  
* List different computational models
Line 34: Line 55:
 
* List applications for automata theory and formal grammar
  
* List applications for automata theory and formal grammar
   
−
=== What should a student be able to understand at the end of the course? ===
 +
==== Level 2: What basic practical skills should a student be able to perform? ====
  +
By the end of the course, the students should be able to ...
−  
−
By the end of the course, the students should be able to describe and explain (with examples)
  
−  
 
* Describe the basic mathematical machinery behind automata theory and how can be applied to programming languages compilers
  
* Describe the basic mathematical machinery behind automata theory and how can be applied to programming languages compilers
 
* Explain Strengths and weaknesses of specific computational model
  
* Explain Strengths and weaknesses of specific computational model
Line 43: Line 62:
 
* Abstract systems using the given models
  
* Abstract systems using the given models
   
−
=== What should a student be able to apply at the end of the course? ===
 +
==== Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios? ====
  +
By the end of the course, the students should be able to ...
−  
−
By the end of the course, the students should be able to apply
  
−  
 
* Formally modelling a system
  
* Formally modelling a system
 
* Reasoning about verification of program properties
  
* Reasoning about verification of program properties
 
* Specifying a system as Finite State Automata, Pushdown Automata or Turing Machine
  
* Specifying a system as Finite State Automata, Pushdown Automata or Turing Machine
 
* Coding in programming languages an emulator of Finite State Automata
  
* Coding in programming languages an emulator of Finite State Automata
−
* Using proof techniques by diagonalization
 +
* Using proof techniques by diagonalization
  +
== Grading ==
   
−
=== Course evaluation ===
 +
=== Course grading range ===
  +
{| class="wikitable"
−  
−
{|
 +
|+
−
|+ Course grade breakdown
  
−
!
  
−
!
  
−
!align="center"| '''Proposed points'''
  
 
|-
  
|-
  +
! Grade !! Range !! Description of performance
−
| Labs/seminar classes
  
−
| 20
  
−
|align="center"| 40
  
 
|-
  
|-
  +
| A. Excellent || 80-100 || -
−
| Interim performance assessment
  
−
| 30
  
−
|align="center"| 30
  
 
|-
  
|-
  +
| B. Good || 65-79 || -
−
| Exams
  
−
| 50
 +
|-
  +
| C. Satisfactory || 50-64 || -
−
|align="center"| 30
  
  +
|-
  +
| D. Poor || 0-49 || -
 
|}
  
|}
   
  +
=== Course activities and grading breakdown ===
−
If necessary, please indicate freely your course’s features in terms of students’ performance assessment: None
  
  +
{| class="wikitable"
−  
  +
|+
−
=== Grades range ===
  
−  
−
<div id="tab:ModelsCourseGradingRange">
  
−  
−
{|
  
−
|+ Course grading range
  
−
!
  
−
!
  
−
!align="center"| '''Proposed range'''
  
 
|-
  
|-
  +
! Activity Type !! Percentage of the overall course grade
−
| A. Excellent
  
−
| 90-100
  
−
|align="center"| 80-100
  
 
|-
  
|-
  +
| Labs/seminar classes || 40
−
| B. Good
  
−
| 75-89
  
−
|align="center"| 65-79
  
 
|-
  
|-
  +
| Interim performance assessment || 30
−
| C. Satisfactory
  
−
| 60-74
  
−
|align="center"| 50-64
  
 
|-
  
|-
−
| D. Poor
 +
| Exams || 30
−
| 0-59
  
−
|align="center"| 0-49
  
 
|}
  
|}
   
  +
=== Recommendations for students on how to succeed in the course ===
   
−
</div>
  
−
If necessary, please indicate freely your course’s grading features: The semester starts with the default range as proposed in the Table [[#tab:ModelsCourseGradingRange|1]], but it may change slightly (usually reduced) depending on how the semester progresses.
  
   
−
=== Resources and reference material ===
 +
== Resources, literature and reference materials ==
   
  +
=== Open access resources ===
 
* Handouts supplied by the instructor
  
* Handouts supplied by the instructor
−
*
 
−
*
 
−
*
  
   
−
== Course Sections ==
 +
=== Closed access resources ===
   
−
The main sections of the course and approximate hour distribution between them is as follows:
  
   
  +
=== Software and tools used within the course ===
−
{|
  
  +
−
|+ Course Sections
  
  +
= Teaching Methodology: Methods, techniques, & activities =
−
!align="center"| '''Section'''
  
  +
−
! '''Section Title'''
  
−
!align="center"| '''Teaching Hours'''
 +
== Activities and Teaching Methods ==
  +
{| class="wikitable"
  +
|+ Activities within each section
  +
|-
  +
! Learning Activities !! Section 1 !! Section 2 !! Section 3
  +
|-
  +
| Development of individual parts of software product code || 1 || 0 || 0
 
|-
  
|-
  +
| Homework and group projects || 1 || 0 || 0
−
|align="center"| 1
  
−
| Automata Theory
  
−
|align="center"| 42
  
 
|-
  
|-
  +
| Midterm evaluation || 1 || 1 || 1
−
|align="center"| 2
  
−
| Formal Grammars
  
−
|align="center"| 24
  
 
|-
  
|-
  +
| Testing (written or computer based) || 1 || 0 || 0
−
|align="center"| 3
  
  +
|-
−
| Computability
  
  +
| Reports || 1 || 1 || 0
−
|align="center"| 24
  
−
|}
 +
|-
  +
| Discussions || 1 || 1 || 1
  +
|}
  +
== Formative Assessment and Course Activities ==
   
−
=== Section 1 ===
 +
=== Ongoing performance assessment ===
−  
−
=== Section title: ===
  
−  
−
Automata Theory
  
−  
−
=== Topics covered in this section: ===
  
−  
−
* Languages
  
−
* Finite State Automata
  
−
* Pushdown Automata
  
−
* Nondeterminism
  
−
* Turing Machines
  
−  
−
=== What forms of evaluation were used to test students’ performance in this section? ===
  
−  
−
<div class="tabular">
  
−  
−
<span>|a|c|</span> &amp; '''Yes/No'''<br />
  
−
Development of individual parts of software product code &amp; 1<br />
  
−
Homework and group projects &amp; 1<br />
  
−
Midterm evaluation &amp; 1<br />
  
−
Testing (written or computer based) &amp; 1<br />
  
−
Reports &amp; 1<br />
  
−
Essays &amp; 0<br />
  
−
Oral polls &amp; 0<br />
  
−
Discussions &amp; 1<br />
  
−  
−  
−  
−
</div>
  
−
=== Typical questions for ongoing performance evaluation within this section ===
  
−  
−
# What is a Finite State Automaton?
  
−
# What is a Pushdown Automaton?
  
−
# What is a Turing Machine?
  
−
# What is a nondeterministic automaton?
  
−
# Given a specific language define a corresponding Finite State Automaton
  
−
# Given a specific language define a corresponding Pushdown Automaton
  
−
# State the difference between Finite State Automata and Pushdown Automata
  
−
# Computing the intersection, union, complement of two automata
  
−
# What is Pumping Lemma? Example of applications.
  
−
# Operations on Automata
  
−  
−
=== Typical questions for seminar classes (labs) within this section ===
  
−  
−
# Check if a given language is recognized by a specific Finite State Automaton
  
−
# Prove with Pumping Lemma that a language is regular
  
−
# Check if a given language is recognized by a specific Pushdown Automaton
  
−
# Check if a given language is recognized by a specific Turing Machine
  
−
# Define a correct automaton given a specific language
  
−  
−
=== Test questions for final assessment in this section ===
  
   
  +
==== Section 1 ====
  +
{| class="wikitable"
  +
|+
  +
|-
  +
! Activity Type !! Content !! Is Graded?
  +
|-
  +
| Question || What is a Finite State Automaton? || 1
  +
|-
  +
| Question || What is a Pushdown Automaton? || 1
  +
|-
  +
| Question || What is a Turing Machine? || 1
  +
|-
  +
| Question || What is a nondeterministic automaton? || 1
  +
|-
  +
| Question || Given a specific language define a corresponding Finite State Automaton || 1
  +
|-
  +
| Question || Given a specific language define a corresponding Pushdown Automaton || 1
  +
|-
  +
| Question || State the difference between Finite State Automata and Pushdown Automata || 1
  +
|-
  +
| Question || Computing the intersection, union, complement of two automata || 1
  +
|-
  +
| Question || What is Pumping Lemma? Example of applications. || 1
  +
|-
  +
| Question || Operations on Automata || 1
  +
|-
  +
| Question || Check if a given language is recognized by a specific Finite State Automaton || 0
  +
|-
  +
| Question || Prove with Pumping Lemma that a language is regular || 0
  +
|-
  +
| Question || Check if a given language is recognized by a specific Pushdown Automaton || 0
  +
|-
  +
| Question || Check if a given language is recognized by a specific Turing Machine || 0
  +
|-
  +
| Question || Define a correct automaton given a specific language || 0
  +
|}
  +
==== Section 2 ====
  +
{| class="wikitable"
  +
|+
  +
|-
  +
! Activity Type !! Content !! Is Graded?
  +
|-
  +
| Question || What is Chomsky Hierarchy? || 1
  +
|-
  +
| Question || What is a Regular language? || 1
  +
|-
  +
| Question || What is a Context-free language? || 1
  +
|-
  +
| Question || What is a Context-sensitive language? || 1
  +
|-
  +
| Question || What is a regular expression? || 1
  +
|-
  +
| Question || Given a specific Finite State Automaton define a grammar for the corresponding language || 0
  +
|-
  +
| Question || Given a specific Pushdown Automaton define a grammar for the corresponding language || 0
  +
|-
  +
| Question || Given a regular expression design the corresponding Finite state Automaton || 0
  +
|-
  +
| Question || Given a Finite state Automaton define the regular expression for the corresponding language || 0
  +
|}
  +
==== Section 3 ====
  +
{| class="wikitable"
  +
|+
  +
|-
  +
! Activity Type !! Content !! Is Graded?
  +
|-
  +
| Question || What is Halting Problem? || 1
  +
|-
  +
| Question || What is Rice theorem? || 1
  +
|-
  +
| Question || What is an undecidable problem || 1
  +
|-
  +
| Question || What is a Turing Machine? || 1
  +
|-
  +
| Question || What is Goedelization? || 1
  +
|-
  +
| Question || Given a specific computational problem showing that it is undecidable (via reduction to a known problem, for example) || 0
  +
|-
  +
| Question || Show a proof via diagonalization of Halting Problem || 0
  +
|-
  +
| Question || Show a proof via diagonalization of Rice Theorem || 0
  +
|-
  +
| Question || Give an example of an undecidable problem || 0
  +
|-
  +
| Question || Show that a Turing Machine with multiple tapes is equivalent to a Turing Machine with a single tape || 0
  +
|}
  +
=== Final assessment ===
  +
'''Section 1'''
 
# Check if a given language is recognized by a specific Finite State Automaton
  
# Check if a given language is recognized by a specific Finite State Automaton
 
# Prove with Pumping Lemma that a language is regular.
  
# Prove with Pumping Lemma that a language is regular.
Line 196: Line 229:
 
# Check if a given language is recognized by a specific Turing Machine
  
# Check if a given language is recognized by a specific Turing Machine
 
# Define a correct automaton given a specific language
  
# Define a correct automaton given a specific language
  +
'''Section 2'''
−  
−
=== Section 2 ===
  
−  
−
=== Section title: ===
  
−  
−
Formal Grammars
  
−  
−
=== Topics covered in this section: ===
  
−  
−
* Chomsky Hierarchy
  
−
* Regular Expressions
  
−
* Relationships with Automata
  
−  
−
=== What forms of evaluation were used to test students’ performance in this section? ===
  
−  
−
<div class="tabular">
  
−  
−
<span>|a|c|</span> &amp; '''Yes/No'''<br />
  
−
Development of individual parts of software product code &amp; 0<br />
  
−
Homework and group projects &amp; 0<br />
  
−
Midterm evaluation &amp; 1<br />
  
−
Testing (written or computer based) &amp; 0<br />
  
−
Reports &amp; 1<br />
  
−
Essays &amp; 0<br />
  
−
Oral polls &amp; 0<br />
  
−
Discussions &amp; 1<br />
  
−  
−  
−  
−
</div>
  
−
=== Typical questions for ongoing performance evaluation within this section ===
  
−  
−
# What is Chomsky Hierarchy?
  
−
# What is a Regular language?
  
−
# What is a Context-free language?
  
−
# What is a Context-sensitive language?
  
−
# What is a regular expression?
  
−  
−
=== Typical questions for seminar classes (labs) within this section ===
  
−  
−
# Given a specific Finite State Automaton define a grammar for the corresponding language
  
−
# Given a specific Pushdown Automaton define a grammar for the corresponding language
  
−
# Given a regular expression design the corresponding Finite state Automaton
  
−
# Given a Finite state Automaton define the regular expression for the corresponding language
  
−  
−
=== Test questions for final assessment in this section ===
  
−  
 
# What is Chomsky Hierarchy?
  
# What is Chomsky Hierarchy?
 
# What is a Regular language?
  
# What is a Regular language?
 
# Given a regular expression design the corresponding Finite state Automaton
  
# Given a regular expression design the corresponding Finite state Automaton
 
# Given a specific Pushdown Automaton define a grammar for the corresponding language
  
# Given a specific Pushdown Automaton define a grammar for the corresponding language
  +
'''Section 3'''
−  
  +
# What is a Turing Machine?
−
=== Section 3 ===
  
−  
−
=== Section title: ===
  
−  
−
Computability
  
−  
−
=== Topics covered in this section: ===
  
−  
−
* Undecidability
  
−
* Halting Problem
  
−
* Rice Theorem
  
−  
−
=== What forms of evaluation were used to test students’ performance in this section? ===
  
−  
−
<div class="tabular">
  
−  
−
<span>|a|c|</span> &amp; '''Yes/No'''<br />
  
−
Development of individual parts of software product code &amp; 0<br />
  
−
Homework and group projects &amp; 0<br />
  
−
Midterm evaluation &amp; 1<br />
  
−
Testing (written or computer based) &amp; 0<br />
  
−
Reports &amp; 0<br />
  
−
Essays &amp; 0<br />
  
−
Oral polls &amp; 0<br />
  
−
Discussions &amp; 1<br />
  
−  
−  
−  
−
</div>
  
−
=== Typical questions for ongoing performance evaluation within this section ===
  
−  
 
# What is Halting Problem?
  
# What is Halting Problem?
 
# What is Rice theorem?
  
# What is Rice theorem?
−
# What is an undecidable problem
  
−
# What is a Turing Machine?
  
−
# What is Goedelization?
  
−  
−
=== Typical questions for seminar classes (labs) within this section ===
  
−  
−
# Given a specific computational problem showing that it is undecidable (via reduction to a known problem, for example)
  
 
# Show a proof via diagonalization of Halting Problem
  
# Show a proof via diagonalization of Halting Problem
 
# Show a proof via diagonalization of Rice Theorem
  
# Show a proof via diagonalization of Rice Theorem
−
# Give an example of an undecidable problem
  
 
# Show that a Turing Machine with multiple tapes is equivalent to a Turing Machine with a single tape
  
# Show that a Turing Machine with multiple tapes is equivalent to a Turing Machine with a single tape
   
  +
=== The retake exam ===
−
=== Test questions for final assessment in this section ===
  
  +
'''Section 1'''
   
  +
'''Section 2'''
−
# What is a Turing Machine?
  
  +
−
# What is Halting Problem?
  
  +
'''Section 3'''
−
# What is Rice theorem?
  
−
# Show a proof via diagonalization of Halting Problem
  
−
# Show a proof via diagonalization of Rice Theorem
  
−
# Show that a Turing Machine with multiple tapes is equivalent to a Turing Machine with a single tape
  

Latest revision as of 12:43, 12 July 2022

Theoretical Computer Science

  • Course name: Theoretical Computer Science
  • Code discipline: BS-
  • Subject area:

Short Description

This course covers the following concepts: Automata Theory; Formal Grammars; Computability.

Prerequisites

Prerequisite subjects

  • CSE113 Logic and Discrete Mathematics: set theory, inductive definitions and proofs, predicate logic, proof techniques (for example by contradiction, diagonalization...), algebraic structures (preferably).

Prerequisite topics

Course Topics

Course Sections and Topics
Section Topics within the section
Automata Theory
  1. Languages
  2. Finite State Automata
  3. Pushdown Automata
  4. Nondeterminism
  5. Turing Machines
Formal Grammars
  1. Chomsky Hierarchy
  2. Regular Expressions
  3. Relationships with Automata
Computability
  1. Undecidability
  2. Halting Problem
  3. Rice Theorem

Intended Learning Outcomes (ILOs)

What is the main purpose of this course?

A good software developer ignorant of how the mechanics of a compiler works is not better than a good pilot when it comes to fix the engine and he will definitively not be able to provide more than average solutions to the problems he is employed to solve. Like automotive engineering teach us, races can only be won by the right synergy of a good driving style and mechanics. Most importantly, limits of computation cannot be ignored in the same way we precisely know how accelerations, forces and frictions prevent us from racing at an unlimited speed. This course will investigate the prerequisites to understand compilers functioning. Although the act of compilation appears deceptively simple to most of the modern developers, great minds and results are behind the major achievements that made this possible. All starts with the Epimenides paradox (about 600 BC), which emphasizes a problem of self-reference in logic and brings us to the short time window between WWI and WW2 when, in 1936, Alan Turing proved that a general procedure to identify algorithm termination simply does not exist. Another major milestone has been reached by Noam Chomsky in 1956 with his description of a hierarchy of grammars. In this long historical timeframe we can put most of the bricks with which we build modern compilers. The course will be an historical tour through the lives of some of the greatest minds who ever lived on this planet.

ILOs defined at three levels

Level 1: What concepts should a student know/remember/explain?

By the end of the course, the students should be able to ...

  • Define a formal language
  • List different computational models
  • Define computational models such as Finite State Automata and Pushdown Automata
  • List different types of Formal Grammars
  • Define computability and related concepts
  • List applications for automata theory and formal grammar

Level 2: What basic practical skills should a student be able to perform?

By the end of the course, the students should be able to ...

  • Describe the basic mathematical machinery behind automata theory and how can be applied to programming languages compilers
  • Explain Strengths and weaknesses of specific computational model
  • Explain Finite State Automata and Pushdown Automata
  • Abstract systems using the given models

Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios?

By the end of the course, the students should be able to ...

  • Formally modelling a system
  • Reasoning about verification of program properties
  • Specifying a system as Finite State Automata, Pushdown Automata or Turing Machine
  • Coding in programming languages an emulator of Finite State Automata
  • Using proof techniques by diagonalization

Grading

Course grading range

Grade Range Description of performance
A. Excellent 80-100 -
B. Good 65-79 -
C. Satisfactory 50-64 -
D. Poor 0-49 -

Course activities and grading breakdown

Activity Type Percentage of the overall course grade
Labs/seminar classes 40
Interim performance assessment 30
Exams 30

Recommendations for students on how to succeed in the course

Resources, literature and reference materials

Open access resources

  • Handouts supplied by the instructor

Closed access resources

Software and tools used within the course

Teaching Methodology: Methods, techniques, & activities

Activities and Teaching Methods

Activities within each section
Learning Activities Section 1 Section 2 Section 3
Development of individual parts of software product code 1 0 0
Homework and group projects 1 0 0
Midterm evaluation 1 1 1
Testing (written or computer based) 1 0 0
Reports 1 1 0
Discussions 1 1 1

Formative Assessment and Course Activities

Ongoing performance assessment

Section 1

Activity Type Content Is Graded?
Question What is a Finite State Automaton? 1
Question What is a Pushdown Automaton? 1
Question What is a Turing Machine? 1
Question What is a nondeterministic automaton? 1
Question Given a specific language define a corresponding Finite State Automaton 1
Question Given a specific language define a corresponding Pushdown Automaton 1
Question State the difference between Finite State Automata and Pushdown Automata 1
Question Computing the intersection, union, complement of two automata 1
Question What is Pumping Lemma? Example of applications. 1
Question Operations on Automata 1
Question Check if a given language is recognized by a specific Finite State Automaton 0
Question Prove with Pumping Lemma that a language is regular 0
Question Check if a given language is recognized by a specific Pushdown Automaton 0
Question Check if a given language is recognized by a specific Turing Machine 0
Question Define a correct automaton given a specific language 0

Section 2

Activity Type Content Is Graded?
Question What is Chomsky Hierarchy? 1
Question What is a Regular language? 1
Question What is a Context-free language? 1
Question What is a Context-sensitive language? 1
Question What is a regular expression? 1
Question Given a specific Finite State Automaton define a grammar for the corresponding language 0
Question Given a specific Pushdown Automaton define a grammar for the corresponding language 0
Question Given a regular expression design the corresponding Finite state Automaton 0
Question Given a Finite state Automaton define the regular expression for the corresponding language 0

Section 3

Activity Type Content Is Graded?
Question What is Halting Problem? 1
Question What is Rice theorem? 1
Question What is an undecidable problem 1
Question What is a Turing Machine? 1
Question What is Goedelization? 1
Question Given a specific computational problem showing that it is undecidable (via reduction to a known problem, for example) 0
Question Show a proof via diagonalization of Halting Problem 0
Question Show a proof via diagonalization of Rice Theorem 0
Question Give an example of an undecidable problem 0
Question Show that a Turing Machine with multiple tapes is equivalent to a Turing Machine with a single tape 0

Final assessment

Section 1

  1. Check if a given language is recognized by a specific Finite State Automaton
  2. Prove with Pumping Lemma that a language is regular.
  3. Check if a given language is recognized by a specific Pushdown Automaton
  4. Check if a given language is recognized by a specific Turing Machine
  5. Define a correct automaton given a specific language

Section 2

  1. What is Chomsky Hierarchy?
  2. What is a Regular language?
  3. Given a regular expression design the corresponding Finite state Automaton
  4. Given a specific Pushdown Automaton define a grammar for the corresponding language

Section 3

  1. What is a Turing Machine?
  2. What is Halting Problem?
  3. What is Rice theorem?
  4. Show a proof via diagonalization of Halting Problem
  5. Show a proof via diagonalization of Rice Theorem
  6. Show that a Turing Machine with multiple tapes is equivalent to a Turing Machine with a single tape

The retake exam

Section 1

Section 2

Section 3

Retrieved from "https://eduwiki.innopolis.university/index.php?title=BSc:_Theoretical_Computer_Science&oldid=7194"