# CS402 Assignment No. 1 Spring 2012 Solution

Q:1
L={###, ##%, ##@, #%@, #%#, #@#, #@%, #%%, #@@, %%%, %%@, %%#, %@%, %#%, %@@, %@#, %##, %#@, @@@, @@#, @@%, @#@, @%@, @##, @#%, @%%, @%#}
Rev of L = {###, %##, @##, @%#, #%#, #@#, %@#, %%#, @@#, %%%, @%%, #%%, %@%, %#%, @@%, #@%, ##%, @#%, @@@, #@@, %@@, @#@, @%@, ##@, %#@, %%@, #%@}
Palindrome = {###, #%#, #@#, %%%, %@%, %#%, @@@, @#@, @%@}
Q:2
a. Consider the language of strings defined over S = {x, z, xy, yz, zx} with the following strings:
i. xyzxyz
ii. xxyzxy
Tokenize the above strings in all possible ways along with finding their lengths.
Ans:-
i.) x,yz,xy,z
xy,zx,yz
x,yz,x,yz
xy,zx,yz
Ans:-
ii.) x,x,yz,xy
x,xy,z,xy
b. Explain whether the above alphabet is valid or invalid along with justification?
Ans:-
i) X,YZ,XY,Z Valid
Because all strings in the alphabet are present in the language of strings S = {x, z, xy, yz, zx}.
Ans:-
ii) X,XY,ZX,Y Invalid
Because “Y” string in the alphabet is not present in the language of strings S = {x, z, xy, yz, zx}, so it is an invalid alphabet.