Bsc CSIT Semester 4 – Theory of Computation – Unit I: Basic Foundations (3 Hrs.)

Question 1

Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.

Marks: 5

Year: 2078 Final TU

Fundamental Concepts in Theory of Computation 1. Alphabet ($\Sigma$) An alphabet is a finite, non-empty set of symbols. It is the basic set from which all strings are formed. Example: The binary a

Question 2

Define string, substring, empty string, and empty language over alphabet {a,b}.

Marks: 5

Year: 2080 Final TU

Let the alphabet be: \[ Σ = \{a, b\} \] 1. String A string is a finite sequence of symbols taken from an alphabet. Example: aab, b, abba are strings over {a, b}. --- 2. Substring A substring is a