Scribd
Upload
102 views3 pages

Computation Theory Assignment Solutions

This document contains an assignment for a computation theory course. It includes 3 questions about finite state automata and regular languages. Question 1 asks students to identify the language recognized by a given automaton T1 and to draw a deterministic finite automaton that recognizes the language {1, 00}. Question 2 contains a true/false statement about the regular language {ε}. Question 3 provides state diagrams for two automata, M1 and M2, and asks students to determine properties of each automaton including start states, accept states, transitions on a given input, and whether each automaton accepts certain strings. The document concludes by providing contact information for the teaching assistant.

Uploaded by

اصيل
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
102 views3 pages

Computation Theory Assignment Solutions

This document contains an assignment for a computation theory course. It includes 3 questions about finite state automata and regular languages. Question 1 asks students to identify the language recognized by a given automaton T1 and to draw a deterministic finite automaton that recognizes the language {1, 00}. Question 2 contains a true/false statement about the regular language {ε}. Question 3 provides state diagrams for two automata, M1 and M2, and asks students to determine properties of each automaton including start states, accept states, transitions on a given input, and whether each automaton accepts certain strings. The document concludes by providing contact information for the teaching assistant.

Uploaded by

اصيل
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Kingdom of Saudi Arabia

‫المملكة العربية السعودية‬


Ministry of Education
‫وزارة التعليم‬
Umm AlQura University
‫جامعة أم القرى‬
Adham University College
‫الكلية الجامعية بأضم‬
Computer Science Department
‫قسم الحاسب اآلل‬

First Semester of 2018-1439/1440H Academic Year

Computation Theory Course, 6803415-3

Assignment One
-Solutions-
Last Delivery Date:
Group One: Tuesday, 25 / 09 / 2018 – 15 / 01 / 1440 H
Group Two: Monday, 24 / 09 / 2018 – 14 / 01 / 1440 H

Question One: 2 Marks


a. What is the language recognized by T1?

b. Find a deterministic finite-state automaton that recognizes the set: {1, 00}
Answer of Question One:
a.
The language recognized by T1 is the set of all strings that contain 11 as a substring.
b.

1
Kingdom of Saudi Arabia
‫المملكة العربية السعودية‬
Ministry of Education
‫وزارة التعليم‬
Umm AlQura University
‫جامعة أم القرى‬
Adham University College
‫الكلية الجامعية بأضم‬
Computer Science Department
‫قسم الحاسب اآلل‬

Question Two: 0.5 Mark


True/ False, with the correction if the statement is false.
a.The language { ε } is not a regular language. ( False )
It is regular because there’s a machine that accepts it:

L( M ) = {}

Question Three: 2.5 Marks


The following are the state diagrams of two DFAs, M1 and M2.
Answer the following questions about each of these machines.

a. What is the start state?


b. What is the set of accept states?
c. What sequence of states does the machine go through on input 01100?
d. Does the machine accept the string 01100?
e. Does the machine accept the string ε?
Answer of Question Three:
a.
M1 M2
q1 q1
b.
M1 M2
{q2} {q2}
c.
M1 M2
q1, q1, q2, q2, q3, q2 q1, q1, q2, q2, q1, q1
d.
M1 M2
Yes, because the input has been consumed and we ended up in a No, because the input has beed consumed and we ended up in a
final state. none final state.
e.
M1 M2
No, it does not because the start state is not an accept state. No, it does not because the start state is not an accept state.

2
Kingdom of Saudi Arabia
‫المملكة العربية السعودية‬
Ministry of Education
‫وزارة التعليم‬
Umm AlQura University
‫جامعة أم القرى‬
Adham University College
‫الكلية الجامعية بأضم‬
Computer Science Department
‫قسم الحاسب اآلل‬

Remember, “Success is 1% inspiration and 99% perspiration” 😉


If you have any questions, feel free to ask me through my email
T.Mariah Sami Ahmed Khayat
Teacher Assistant @ Adam University College
mskhayat@uqu.edu.sa

You might also like