[go: up one dir, main page]
Scribd
Upload
323 views5 pages

Arsdigita University Month 8: Theory of Computation Professor Shai Simonson Exam 1 (50 Points)

Uploaded by

brightstudent

This document contains an exam for a theory of computation class. The exam has 5 questions covering topics like finite state machines, regular expressions, regular and non-regular languages, closure properties of regular languages, and decision algorithms for regular languages. Question 1 has 3 parts about finite state machines. Question 2 asks to draw a finite state machine for a complement language. Question 3 determines if 3 given languages are regular or not with proofs. Question 4 determines closure properties for 2 operations on regular languages. Question 5 gives an algorithm to decide if a regular language shares strings with another described by a regular expression.

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt

Arsdigita University Month 8: Theory of Computation Professor Shai Simonson Exam 1 (50 Points)

Uploaded by

brightstudent
323 views5 pages
This document contains an exam for a theory of computation class. The exam has 5 questions covering topics like finite state machines, regular expressions, regular and non-regular languages, closure properties of regular languages, and decision algorithms for regular languages. Question 1 has 3 parts about finite state machines. Question 2 asks to draw a finite state machine for a complement language. Question 3 determines if 3 given languages are regular or not with proofs. Question 4 determines closure properties for 2 operations on regular languages. Question 5 gives an algorithm to decide if a regular language shares strings with another described by a regular expression.

Original Description:

automata

Original Title

automata exam

Copyright

© © All Rights Reserved

Available Formats

PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

This document contains an exam for a theory of computation class. The exam has 5 questions covering topics like finite state machines, regular expressions, regular and non-regular languages, closure properties of regular languages, and decision algorithms for regular languages. Question 1 has 3 parts about finite state machines. Question 2 asks to draw a finite state machine for a complement language. Question 3 determines if 3 given languages are regular or not with proofs. Question 4 determines closure properties for 2 operations on regular languages. Question 5 gives an algorithm to decide if a regular language shares strings with another described by a regular expression.

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
323 views5 pages

Arsdigita University Month 8: Theory of Computation Professor Shai Simonson Exam 1 (50 Points)

Uploaded by

brightstudent
This document contains an exam for a theory of computation class. The exam has 5 questions covering topics like finite state machines, regular expressions, regular and non-regular languages, closure properties of regular languages, and decision algorithms for regular languages. Question 1 has 3 parts about finite state machines. Question 2 asks to draw a finite state machine for a complement language. Question 3 determines if 3 given languages are regular or not with proofs. Question 4 determines closure properties for 2 operations on regular languages. Question 5 gives an algorithm to decide if a regular language shares strings with another described by a regular expression.

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 5

ArsDigita University

Month 8: Theory of Computation


Professor Shai Simonson
Exam 1 (50 points)
1. (15 points) Finite State Machines.
Consider the following NFA over the alphabet {0,1}:
a. Convert this NFA to a minimal DFA.
b. Write a regular expression for the set the machine accepts.
c. Write a linear grammar where each right side is of the form aB or a.
(a a terminal and B a non-terminal) to generate the set.
2
2. (5 points) More Machines
Draw a finite state machine that accepts the complement of the language accepted by
the non-deterministic machine below:
3
3. (15 points) Regular or Not, Here I Come.
Determine and prove for each set below whether it is Regular or not. Be careful.
a. The set of all strings in which every third symbol is the same as the first symbol in
the string.
b. The set 1
m
0
n
1
m+n
, for m and n greater than or equal to one.
c. The set of strings where each string has an equal number of 0s and 1s, and every
prefix of the string has at most one more 0 than 1, and at most one more 1 than 0.
4
4. (10 points) Closure.
Determine whether Regular sets are closed under each of the operations below. Prove
your answers by an explanation and/or example or counterexample.
a. Even(L) is the set of all strings x in L such that |x| is even.
b. Triple(L) = {x | x=uvw, such that u, v, w are in L, and |u| = |v| = |w|}.
5
5. (5 points) Decision Algorithms.
Give a decision algorithm to determine whether a regular language L has one or more
strings in common with the language described by the regular expression
[00 + 11 + (01 + 10)(00 + 11)*(01 + 10)]*.

You might also like