CS402 Spring 2012 Assignmet_1

Theory of Automata (CS402)

Assignment # 1(Solution)

  Total marks = 20

                                                                                       Deadline Date = Expired

Please carefully read the following instructions before attempting the assignment.

Rules for Marking

It should be clear that your assignment would not get any credit if:

• The assignment is submitted after due date.
• The submitted assignment does not open or file is corrupt.
• The assignment is copied. Note that strict action would be taken if the submitted assignment is copied from any other student. Both students will be punished severely.

1)      You should concern recommended books to clarify your concepts as handouts are not sufficient.

2)      You are supposed to submit your assignment in .doc format. Any other formats like scan images, PDF, Zip, rar, bmp, docx etc will not be accepted.

3)      You are advised to upload your assignment at least two days before Due date.

4)      This assignment file comprises of Two (3) pages.

Important Note: 

Assignment comprises of 20 Marks. Note that no assignment will be accepted after due date via email in any case (whether it is the case of load shedding or emergency electric failure or internet malfunctioning etc.). Hence, refrain from uploading assignment in the last hour of the deadline, and try to upload Solutions at least 02 days before the deadline to avoid inconvenience later on.

For any query please contact: CS402@vu.edu.pk

Q 1.

a. Define the language of strings of length 3 over Σ = {#, %, @}.                 Marks 4

Ans.

            L = {###, ##%, ##@, #%#, #@#, #%%, #@%, #@@, #%@, %##, %#%, %#@, %%#, %@#, %@%, %%%, %%@, %@@, @###, @#%, @#@, @%#, @%%, @%@, @@#, @@%, @@@ }       

b. Generate the reverse of language generated in part a.                             Marks 4

Ans.

            Rev (L) = {###, %##, @##, #%#, #@#, %%#, %@#, @@#, @%#, ##%, %#%, @#%, #%%, #@%, %@%, %%%, @%%, @@%,##@, %#@, @#@, #%@, %%@, @%@, #@@, %@@, @@@}

c. Identify if there is any palindrome.                                                                          Marks 2

Ans.

            Palindromes= {###, #%#, #@#, %#%, %@%, %%%, @#@, @%@, @@@}

                                   

                                                                                                                              

Q 2.

Consider the language of strings defined over Σ = {x, z, xy, yz, zx} with the following strings:

i.  xyzxyz

ii. xxyzxy

a. Tokenize the above strings in all possible ways along with finding their lengths.                                                                                                                                          Marks 6

Ans.

i.  xyzxyz

The give string can be tokenized in the following four ways:

Tokenization                 Length

(x)(yz)(x)(yz)                4         

(xy)(zx)(yz)                   3

(x)(yz)(xy)(z)                4

(xy)(z)(x)(yz)                4

ii. xxyzxy

The string can be tokenized in the following two ways:

Tokenization                 Length

(x)(x)(yz)(xy)                  4

(x)(xy)(z)(xy)                 4

b. Explain whether the above alphabet is valid or not along with justification?

Marks 4

Ans.

The given alphabet Σ = {x, xy, yz, zx} is an invalid alphabet because “x” is the prefix of “xy” and “z” is the prefix of “zx” where x and z are already letters of the given alphabet set.  From the definition of invalid alphabet we know that an alphabet set is invalid if there is a letter which is the letter of the alphabet set and is the prefix of another letter.