Get premium membership and access revision papers, questions with answers as well as video lessons.

Got a question or eager to learn? Discover limitless learning on WhatsApp now - Start Now!

Cisy 402:Cisy 402 Automata And Formal Languages Question Paper

Cisy 402:Cisy 402 Automata And Formal Languages

Course:Computer Science

Institution: Kenya Methodist University question papers

Exam Year:2012

KENYA METHODIST UNIVERSITY

END OF 3RD TRIMESTER 2012 (EVENING) EXAMINATIONS

FACULTY : COMPUTING AND INFORMATICS
DEPARTMENT : COMPUTER SCIENCE AND BUSINESS
INFORMATION
UNIT CODE : CISY 402
UNIT TITLE : AUTOMATA AND FORMAL LANGUAGES
TIME : 2 hours

Instructions:
• Answer question one and any other two questions.
Question One
(a) Let ? be an alphabet. (6 marks)
i. Define a deterministic finite automata on ?.
ii. Explain what is the language determined by such a finite automation.
iii. Explain why such a language is a context free language.
(b) Build A DFA corresponding to the regular expression (ab)*+a*. (6 marks)
(c) Prove by induction 12+22+32+n…+n2=n(n+1)(n+2) (5 marks)
6

(d) Find the shortest string that is not in the language represented by the regular expression a*(ab)*b* (5 marks)
(e) Define the following terms:
i. Alphabet
ii. Word
iii. String
iv. Language (8 marks)
Question Two
(a) Convert the following NFA- to DFA (10 marks)

b a

b
a

ii.

a,b

a,b

c a,b

ab

c

Question Three
(a) Describe the three properties of closure of regular expressions. (15 marks)
(b) Find a regular expression corresponding to the language of all strings over the alphabet {a,b} than contain exactly three a’s (5 marks)
Question Four
Discuss with proper examples, five types of turing machines. (20 marks)

More Question Papers

Birs 111 : Critical And Creative Thinking

Cisy 432:Distributed Systems

Bbit 232:Database Systems

Bbit 241 Cisy 131 (Computer Networks / Telecommunication Networks)(2 Trimester 2016)

Cisy 332:Network Hardware And Configuration

Computer Networks (Bbit 241) (Cisy 131) (Dbit 223) (Dcis 121) 1St Trimester 2016

Database Management (Bbit 232) (Cisy 221) 2Nd Trimester 2015

Database Systems (Bbit 232) (Cisy 221) (Comp 340) (Bsis 115) (Dbit 221) (Dcis 106) 3Rd Trimester 2014

E-Commerce (Bbit 436) (Cisy 428) 1St Trimester 2016

E-Commerce (Bbit 436) (Cisy 428) 2Nd Trimester 2015

E-Commerce (Bbit 436) (Cisy 428) 3Rd Trimester 2015

Human Computer Interraction (Bbit 314) (Bsis 430) 2Nd Trimester 2012

Introduction To Computer Networks (Bbit 241) (Cisy 131) 2Nd Trimester 2014

Introduction To Computer Networks (Cisy 131) (Bbit 241) (Dbit 223) (Dcis 121) 2Nd Trimester 2015

Introduction To Information Systems (Bbit 111) 2Nd Trimester 2012

Introduction To Sociology (Sost 131) 1St Trimester 2015

Introduction To Sociology(Sost 131)2Nd Trimester 2016

Object Oriented Analysis And Design (Bbit 335) (Cisy 411) 3Rd Trimester 2014

Object Oriented Programming (Bbit 223) (Cisy 210) (Dcis 120) 2Nd Trimester 2014

Principles Of Marketing (Mktg 218) 2Nd Trimester 2014

Principles Of Marketing (Mktg 218) 2Nd Trimester 2017

Simulation And Modeling (Bbit 417) (Cisy 403) 3Rd Trimester 2014

System Analysis And Design(Bbit 231)( Cisy 222)( Dbit 124)( Dcis 104)2Nd Trimester 2016

Systems Analysis And Design (Bbit 231) (Cisy 221) 1St Trimester 2017

Systems Analysis And Design (Bbit 231) (Cisy 222) 1St Trimester 2015

(Cisy 433) (Bbit 447): Cryptopraphy And Network

(Lang 310:Varieties Of English

A T R (Theo 205)

Abnormal Psychology (Coun 125)

Abnormal Psychology B(Coun 125)

Abnormal Psychology(Coun 125)

Accf 330Intermediate Accounting 1

Accf 430Financial Management Ii

Accf 431 Tax Planning And Management

Accf 431: Taxation

Accf 431: Taxation

Accf 432Auditing 1

Accf 434: Auditing Ii

Accommodation Management (Bhtm 308) (Bshm 212)

Accounting Information Systems (Bbit 437)

Accounting Information Systems I(Bbit 311)

Accounting Information Systems(Bbit 311)

Accounting Information Systems(Bbit 447)

Accounting Information Systems(Buss 344)

Acct 010 :Principles Of Accounting

Acct 112: Principles Of Accounting 1

Acct 112: Principles Of Accounting 1

Acct 112: Principles Of Accounting 1

Acct 112: Principles Of Accounting 1

Acct 112: Principles Of Accounting 1

Popular Exams

Return to Question Papers

Quick Links