date: 2024-10-30
title: "TOC-As-2"
status: DONE
author:
  - AllenYGY
tags:
  - Assignment
  - TOC
publish: True

TOC-As-2

Question 1

Convert the following NFA into an equivalent DFA. (20 pt)

First iteration

Second iteration

Third iteration

twQhiy

Question 2

Let . Give a regular expression for each of the following language. (10 pt for each)

2.a. .

2.b. .

Question 3

Determine whether the following languages over are regular. Prove your answer. Each question has two languages. You don’t need to do both, select one at your favor. In general, the original languages are difficult, the alternative ones are easy. You have your own choice. If you do both, we mark the easy one. (10 pt for each subquestion)

3.a.

is not regular.

Assume is regular. Suppose , Let , which is a string in

By the pumping lemma, is in the form . The substring can be of the following three cases.

If only consists 's
- Suppose consists of .
  - Then or
  - , which is not in .
If only consists 's
- Suppose consists of .
  - Then
  - , which is not in .
If consists both 's and 's
- Then and in are intersecting with each other, which is not in the form of Thus, .

3.b.

is not regular.

Assume is regular. Suppose , Let , which is a string in

By the pumping lemma, is in the form . The substring can be of the following three cases.

If only consists of 's
- Suppose consists of .
  - Then ,
    - , which is not in .
  - Or
    - , which is not in .
If only consists of 's
- Suppose consists of .
- then
  - , which is not in .
If consists of both 's and 's
- Then and in are intersecting with each other, which is not in the form of Thus, .

3.c.

is not regular.

Assume is regular. Suppose , , Let , which is a string in

By the pumping lemma, is in the form . The substring can be of the following three cases.

If only consists of 's
- Suppose consists of .
  - Then ,
    - , which is not in .
  - Or
    - , which is not in .
If only consists of 's
- Suppose consists of .
  - Then
  - , which is not in .
If consists of both 's and 's
- Then and in are intersecting with each other, which is not in the form of Thus, .

3.d.

is regular.

Since contains every possible string of (all strings with some number of followed by some number of ), this language is equivalent to:

Therefore, I can construct a NFA that accepts this language.

3.d.

Question 4

Are the following languages regular? Prove your answer. (10 pt for each)

4.a.

is not regular.

can be divided into two parts.
and

is not regular.
Assume is regular.
Suppose , Let , which is a string in

By the pumping lemma, is in the form . The substring can be of the following three cases.

If only consists of 's
- Suppose consists of .
  - Then
  - , which is not in .
If only consists of 's
- Suppose consists of .
  - Then
  - , which is not in .
If consists of both 's and 's
- Then and in are intersecting with each other, which is not in the form of Thus, .

is regular, because

Although is regular, is the union of and , and is not regular.
we can not construct a NFA for . Thus, is not regular.

4.b.

is not regular.

can be divided into two parts. and .
Let and

is not regular, the proof has been shown in the previous question.

is not regular.
Assume is regular. Suppose , Let , which is a string in

By the pumping lemma, is in the form . The substring can be of the following three cases.

If only consists of 's
- Suppose consists of .
  - Then
  - , which is not in .
If only consists of 's
- Suppose consists of .
  - Then
  - , which is not in .
If consists of both 's and 's
- Then and in are intersecting with each other, which is not in the form of Thus, .

is not regular. is also not regular.

is not regular, we can not construct a NFA for . Thus, is not regular.