TA ASSIGNMENT 1 Part 1

Theory of Automata

Assignment #1

Part #1

Recursive Definition #1:

Language of multiples of 3

Step 1#- 3 and 6 are multiples of 3

Step 2#- If x is in L then 3x is multiple of three

Step 3#- No words except generated above can be considered as multiple of 3

Recursive Definition #2:

Language of 2^n

Step 1#- 1 and 2 are multiples of 3

Step 2#- If x is in L then x*2 is also in Language

Step 3#- No words except generated above can be considered as member of                    Language.

Recursive Definition #3:

Language of strings ending on c defined on Σ={a,b,c}

Step 1#- c is in L

Step 2#- If x is in L then xc is also in L

Step 3#- No words except generated above can be considered as member of                    Language.

Recursive Definition #4:

Language of strings having ab defined on Σ={a,b}

Step 1#- ab is in L

Step 2#- If x is in L then xabx is also in L

Step 3#- No words except generated above can be considered as member of                    Language.

Recursive Definition #5:

Language of strings beginning and ending on same letter Σ={a,b}

Step 1#- a and b 

Step 2#- If x is in L then axa and bxb are also in L where x belongs to Σ*

Step 3#- No words except generated above can be considered as member of                    Language.

To be continued