Contact on: info@huryy.com

# ASSIGNMENT 1: AUTOMATA THEORY ASSIGNMENT 1: CSC 313: AUTOMATA THEORY

INSTRUCTIONS: Attempt all the questions. To be done in groups of 5 – 7 students. [30 Marks]

Tips Become Successful in your career and Achieve What You Want in Life

## Question One:

a) Describe what a pushdown automaton (PDA) is, distinguishing it from a deterministic finite automata

b) Let S be the set defined by 0, 3 ∈ S, and if x and y ∈ S, then x+y ∈ S.

Use mathematical induction to show that every natural number that is a multiple of 3 is an element of S

c) Show that the following language is context-free using the Pumping Lemma

L = { ( 0n 1n )n | n≥1 }

## Question Two:

a) Given the sets: U  {1, 2, 3, 4, 5, 6, 7, 8} B  {2, 3, 5, 6}

Set B is a subset of set U. What is the complement of set B?

b) In a group of 700 people 600 can speak English and 500 can speak Swahili. If all the people can speak at least one of the two languages, find:

i) How many can speak both languages?

ii) How many can speak exactly one language

## Question Three:

a) Describe the language accepted by the following grammar

i. S → abS | a
ii. S → aSb | ε

b) Write the grammar for the following language expressions

i. axby, where x = 3y
ii. axby, where x = 2y