cs402 assignment 1 2023 | CS402 assignment 1 solution 2023 | CS402 | sir yousaf sadiq

Theory of Automata (CS402)
Assignment # 01
Fall 2023
LIKE ,comment and subscribe

Total marks = 20
Deadline
15^th of November 2023

Please carefully read the following instructions before attempting the assignment.
CS402 Assignment 2 solution 2023 made by YOusaf Sadiq
RULES FOR MARKING
It should be clear that your assignment would not get any credit if:
The assignment is submitted after the due date.
Strict action will be taken if the submitted solution is copied from any other student or the internet.

You should consult the recommended books to clarify your concepts as handouts are not sufficient.

UPLOADING INLINE ASSIGNMENT INSTRUCTION
Follow the given instructions to submit Inline assignments:
Microsoft Word (doc/docx) and Adobe Acrobat (pdf) file uploading options will not be available in inline assignment submission.
·        Students can submit HTML, Images, and plain text only in this inline Mode. You may also insert an image file/table.
·        Students can insert the images or snapshots in the following formats.
·       Images and tables can be inserted using the following highlighted option in the interface.
Topic Covered:
·       Alphabets, Strings
·       Tokenization
·       Reverse of String
·       Regular Expression
·       Finite Automaton

Lecture # 01 till Lecture # 07

NOTE

No assignment will be accepted after the due date via email in any case (whether it is the case of load shedding or internet malfunctioning etc.). Hence refrain from uploading assignments in the last hour of the deadline. It is recommended to upload the solution at least two days before its closing date.

If you people find any mistake or confusion in the assignment (Question statement), please consult with your instructor before the deadline. After the deadline, no queries will be entertained in this regard.

For any query, feel free to email me at:
cs402@vu.edu.pk

Question No 01                                                                                                                            Marks (4+6=10)
a)     Determine which of the following sets have valid/invalid alphabets:
Σ1= {a, ab, b, d, be}
Σ2= {a, bc, ce, da}

Σ1:
1.     'a' is a valid symbol, so it's part of the alphabet.
2.     'ab' is not a valid symbol because it contains more than one character. It should consist of individual symbols from the alphabet.
3.     'b' is a valid symbol.
4.     'd' is a valid symbol.
5.     'be' is not a valid symbol because it contains more than one character. It should consist of individual symbols from the alphabet.
Σ2:
1.     'a' is a valid symbol, so it's part of the alphabet.
2.     'bc' is not a valid symbol because it contains more than one character. It should consist of individual symbols from the alphabet.
3.     'ce' is not a valid symbol because it contains more than one character. It should consist of individual symbols from the alphabet.

4.     'da' is not a valid symbol because it contains more than one character. It should consist of individual symbols from the alphabet.

In both cases, neither Σ1 nor Σ2 is a valid alphabet as they contain strings that are not composed of individual symbols

b)     Consider Σ= {a, bac, ca, de, f} to find the length of the string s=bacdeacadef by tokenizing. Give its reverse Rev (s).

s = "bacdeacadef"
Tokenization:
1.     "bac" is a valid token from Σ.
2.     "de" is a valid token from Σ.
3.     "a" is a valid token from Σ.
4.     "ca" is a valid token from Σ.
5.     "de" is a valid token from Σ.
6.     "f" is a valid token from Σ.

So, the tokenization of s is: ["bac", "de", "a", "ca", "de", "f"].

Now, to find the reverse Rev(s), we reverse the order of these tokens:
Rev(s) = ["f", "de", "ca", "a", "de", "bac"]

The reverse of s, using the given alphabet and tokenization, is "fdecaadebac."

Question No 01                                                                                                                            Marks (5+5=10)
a)     Write the regular expression for a language of all words starting with “1” and ending with “0” having “01” as a substring over the set of alphabets Σ={1,0}.
1(0+1)01(0+1)0

b)     Draw the Finite Automaton for the above language.

Use this URL FOR DIAGRAM OF FINITE AUTOMATA (FA)

https://ivanzuzak.info/noam/webapps/fsm_simulator/

DOWNLOAD FILE

Comments