Scribd
Upload
82 views4 pages

Assignment TWO: Computation Theory Course, 6803415-3

This document contains an assignment for a Computation Theory course with four questions and their answers. The questions cover topics like: 1) Converting a finite automaton to a regular expression 2) Drawing state diagrams for non-deterministic finite automata (NFAs) recognizing specific languages 3) Converting an NFA to an equivalent deterministic finite automaton (DFA) 4) Choosing the correct regular expression for a specific language The document provides the questions, answers, and some explanatory details. It is a homework assignment with computational theory concepts.

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
82 views4 pages

Assignment TWO: Computation Theory Course, 6803415-3

This document contains an assignment for a Computation Theory course with four questions and their answers. The questions cover topics like: 1) Converting a finite automaton to a regular expression 2) Drawing state diagrams for non-deterministic finite automata (NFAs) recognizing specific languages 3) Converting an NFA to an equivalent deterministic finite automaton (DFA) 4) Choosing the correct regular expression for a specific language The document provides the questions, answers, and some explanatory details. It is a homework assignment with computational theory concepts.

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/ 4

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 TWO
-Solutions-
Last Delivery Date:
Group One: Tuesday, 09 / 10 / 2018 – 29 / 01 / 1440 H
Group Two: Monday, 08 / 10 / 2018 – 28 / 01 / 1440 H

Question One: 1 Mark


Convert the following finite automata to regular expression.

Answer of Question One:

So, the regular expression is (𝒂 ∗ 𝒃)(𝒂 ∪ 𝒃𝒂 ∗ 𝒃)∗

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

Question Two: 2 Marks


Give state diagrams of NFAs with the specified number of states recognizing the following
languages. The alphabet is {0,1}.
a. The language {w| w ends with 00} with three states.
b. The language {ε} with one state.
Answer of Question Two:
a)

b)

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

Question Three: 1 Mark


Convert the following nondeterministic finite automata to equivalent deterministic finite
automata.

Answer of Question Three:

The state transition table for NFA:


q 𝜹(𝒒, 𝒂) 𝜹(𝒒, 𝒃)
1 {1,2} 2
2 ∅ 1

The state transition table for DFA:


q 𝜹(𝒒, 𝒂) 𝜹(𝒒, 𝒃)
1 {1, 2} 2
{1, 2} {1, 2} {1, 2}
2 ∅ 1
∅ ∅ ∅

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

Answer of Question Three:


The equivalence DFA state diagram:

a, b

∅
1

b
a
b
a

2
{1,2}
a, b

Question Four: 1 Mark


Choose the best answer.
1. The regular expression that generate the language: {w ∈Σ ∗ | |w| is odd}, where the alphabet is Σ =
{a, b} is ………………
a) (a ∪ b)∗ ((a ∪ b)(a ∪ b))∗
b) (a ∪ b) ((a ∪ b)(a ∪ b))∗
c) b ∗ a(ab ∗ a ∪ b)∗
d) (a ∪ b) ∗ (aa ∪ bb)

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
[email protected]

You might also like