Theory of Computation : Homework Problems & Solution

1. A Language is given by L = {xxx, xxy, xyx, xyy, yxx, yxy, yyx, yyy}. Identify the Strings, Alphabet and Symbols for this Language.

Strings are: xxx, xxy, xyx, xyy, yxx, yxy, yyx, yyy

Alphabet is: {x,y}

Symbols are: x and y

2. Give two examples each of an Infinite Language and a Finite Language.

Example of an Infinite Language: Set of all strings over {0,1} that begin with 1. Which is {1, 11, 10, 100, 101, 111, 1000, 1001, 1010,....}

Example of a Finite set: Set of all all strings over {a,b} of length 2. Which is {aa,ab,ba,bb}

3. If $\sum={\left\lbrace{a},{b}\right\rbrace}$, define and write the values of $\sum^0$, $\sum^1$ and $\sum^2$. Also write the values of $\sum^{\ast}$ and define $\sum^{\ast}$

$\sum^{0}={\left\lbrace\epsilon\right\rbrace}$

$\sum^1$ = {a,b}

$\sum^2$ = {aa,ab,ba,bb}

$\sum^{\ast}=\sum^{0}\cup\sum^{1}\cup\sum^{2}\cup\sum^{3}\cup\ldots.$

$\sum^{\ast}$ can be defined as the set of all possible of all lengths over $\sum^{\ast}$