Theory of Computation · Unit 1 · 3 hrs
Basic Foundations
Exam-focused notes for Basic Foundations (Theory of Computation, CSC262): what the TU syllabus asks and how it has actually been tested, with 4 solved past questions from this unit.
What this unit covers
- Review of Set Theory
- Logic
- Functions
- Proofs
- Automata, Computability and Complexity
- Complexity Theory
- Computability Theory
- Automata Theory
- Basic concepts of Automata Theory
- Alphabets
- Power of Alphabet
- Kleen Closure Alphabet
- Positive Closure of Alphabet
- Strings
- Empty String
- Substring of a string
- Concatenation of strings
- Languages
- Empty Language
Positive Closure of Alphabet
Does machine always refer to hardware? Justify. Define positive closure and Kleene closure. [5]
--- No, a machine does not always refer to hardware. In the context of Theory of Computation (TOC), the term "machine" refers to an abstract model rather than a physical hardware device. Abstract Model: An abstract model of a computer system is considered e...
Full solved answer →Differentiate Kleen closure from positive closure. Compute positive and Kleen closure of {ab}. [5]
- Set: $\{ab\}$ (a set containing a single element, the string "ab") - Required: differentiate Kleene closure from positive closure; compute both for $\{ab\}$. Property Kleene Closure ($L^$) Positive Closure ($L^+$) --------- Definition All strings formed b...
Full solved answer →Strings
Define string, substring, empty string, and empty language over alphabet {a,b}. [5]
A string (also called a word) is a finite sequence of symbols taken from an alphabet. Over the alphabet Σ = {a, b}, a string is any finite arrangement of the symbols a and b. Examples over {a, b}: - a - b - ab - aab - bba - abab Formally, if Σ = {a, b}, the...
Full solved answer →Alphabets
Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example. [5]
--- An alphabet is a finite, non-empty collection (set) of symbols. It is usually denoted by Σ. Example: - Σ = {a, b, c} - Σ = {0, 1} --- A string p is called a prefix of a string w if it is obtained by removing zero or more trailing symbols of w. Example: ...
Full solved answer →Make Unit 1 stick
Practice CSC262 with flashcards & quizzes