# CS402 Assignment 1 Solution Fall 2021 - Theory of Automata Assignment

VU Answer Provide Latest CS402 Assignment 1 Solution Fall 2021. Easy to See Complete Perfect CS402 New Assignment 1 Solution 2021 and Download PDF File.

## CS402 ASSIGNMENT 1 SOLUTION FALL 2021

Due Date: 14 Dec 2021

Total Marks: 20

Topic Covered:

The objective of this assignment is to assess the understanding of students about:

Languages

Regular Expression

Finite automata

Question 1:

Part a:

Determine which of the following sets have valid/invalid alphabets:

Σ1={ a, ab, b, d, ae}

Σ2={a, ba, c, d}

Solution:

 Ways s = abbaaabdbbaa 1 ∑ 1 = {a, ab, b, d, ae} ∑ 1 = {a, ba, c, d} 2 a b b a a a b d b b a a b b a a a b d b b a a Ab b a a a b d b b a a b ba a a b d b b a a Valid AlphbetsWe have tried two different ways to tokenize the string and it was successfully with ∑ 1 Invalid AlphabetsThis is because we cannot tokenize letters according to ∑ 1 . This character (b) does not belong from ∑ 1 character.

Part b:

Consider Σ={ ab, baa, c, db} to find the length of the string s=abbaaabdbbaa by tokenizing. Give its reverse Rev (s).

Solution:

s = abbaaabdbbaa

Tokenized = (ab) (baa) (ab) (db) (baa)

Length = 5

Rev (s) = (baa) (db) (ab) (baa) (ab)

Rev (s) = baabdabbaaab

Question 2:

Part a:

Give the regular expression RE over Σ={a,b} for the language of all words having b as a second letter.

Solution:

(a + b) b + (a + b) *

Part b:

What will be the Finite Automata for the above language?

Solution:

Diagram Solution File Given Below in PDF File.