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 }

##### How to start an online business.

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

- How to Become a Data Analyst – Salary, Qualifications, skills.How to Become a Data Analyst – Salary, Qualifications, skills. Hello, hope you are doing great. Let’s start by defining what a data analyst is? Whether it’s sales figures, audience demographics, and market research, or keeping track of their overheads, every business, regardless of size, records some kind of data. It’s a Data Analysts’ job…
- The truth about Crypto-Currency.The truth about Crypto-Currency. What to Know About Cryptocurrency. What is cryptocurrency? Cryptocurrency is a type of digital currency that generally only exists electronically. There is no physical coin or bill unless you use a service that allows you to cash in cryptocurrency for a physical token. You usually exchange cryptocurrency with someone online, with…
- Basic Computer OperationsBasic Computer Operations. A computer as shown in the figure below performs basically five major operations or functionsirrespective of its size and make. These are 1) it accepts data or instructions by way of input, 2)it stores data, 3) it can process data as required by the user, 4) it gives results in the form…
- Classification of ComputersClassification of Computers. i. Classification of Computers by Size a) Micro-Computers • Micro –Computers are the Smallest class of Computers• Micro- Computers have one micro-processor in its Central Processing Unit• Micro-Processor refers to Central Data Processing Unit of a Micro-Computers• Micro- Computers can serve one user at ago.• Micro- Computers are commonly used in modern…
- History of ComputersHistory of Computers i. First generation computers (1946-1956) Overview of the Intelligent System They made use of vacuum tubes to store and process information. The tubesconsumed a lot of power and generated a lot of heat (overheating). They were huge insize and occupy a room. They used magnetic tape. Storage capacity was very low i.e.2kb…