COS3701 Theoretical Computer Science III (COS3701)

FORMAL LANGUAGES AND AUTOMATA THEORY

TERMS: i. FSM: Finite State Machine (Lowest level machine, basic computations) ii. CFL: Context Free Language (Capable of a little higher level computations) iii. TM: Turing Machine (High Level Computations) iv. Undecidable: Problems that cannot be solved by any machine v. Symbol examples: a, b, c, 0, 1, 2, 3.... vi. Alphabet: denoted by 'sigma': collection of symbols eg. {a,b} or {d, e, f, g} or {0, 1, 2} vii. String: sequence of symbols eg.a,b,0, aa, bb, ab, 01 viii. Language: Set ...

COURSE: THEORETICAL COMPUTER SCIENCE III COURSE CODE: COS3701 SEMESTER: 2021 01 ASSIGNMENT: 01 UNIQUE NUMBER: DUE DATE: 15 TH MAY 2021 COS3701 REG. NO UNIQUE NO: Page 1 of 10 1. Problem 3(ii) on page 255. Consider the CFG S → XaXaX X → aX|bX|Λ What is the language this CFG generates? This CFG can generate (a+b)*a(a+b)*a(a+b)*. We can thus verify the language as follows: ▪ The CFG S → XaXaX only generates words that contain as, therefore the grammar only generates wor...

COS3701 - SUMMARIZED EXAM NOTES 2021. Theoretical Computer Science III. Theory of Computation 4 Mustansiriya University – college of sciences – computer science department – second class Language language is the set of all strings of terminal symbols derivable from alphabet. alphabet is a finite set of symbols. For example {0, 1} is an alphabet with two symbols, {a, b} is another alphabet with two symbols and English alphabet is also an alphabet. A string (also called a word) is a fin...

COS3701 STUDY NOTES

Feedback on EXAM PREPARATION PHASE IV (Use The Pumping Lemma) Question 1: Show that the language {anb n c nd n for n = 1 2 3 . ..} = { abcd aabbccdd . . . } is non-context-free. Feedback Question 1: In order to answer this question we use the pumping lemma with length. See study guide. In this question the alphabet is ∑= {a; b; c; d}. • The first step is to assume that the language L = {a nb nc nd n | n = 1, 2, 3…} actually is context-free. This means that there exis...