Tutorial No 1 Date:13/01/25

Chapter 1:Introduction to AT and Regular Expression

1. Regular Expression for no 0 or many triples of 0’s and many 1 in the strings.
2. RegExp for strings of one or many 11 or no 11.
3. Regular expressions for all non empty strings
4. Regular expressions over {a, b} for all non empty strings of even length
5. Regular expressions for all non empty strings of odd length
6. A regular expression for ending with abb
7. A regular expression for all strings having 010 or 101.
8. Regular expression for Even Length Strings defined over {a,b}
9. Regular Expression for strings having at least one double 0 or double 1.
10. Regular Expression of starting with 0 and having multiple even 1’s or no
1.
11. Regular Expression for an odd number of 0’s or an odd number of 1’s in
the strings.
12. Regular Expression for having strings of multiple double 1’s or null.
13. Regular Expression (RE) for starting with 0 and ending with 1.
14. RE for ending with b and having zero or multiple sets of aa and bb.
15. A regular expression of the second last symbol is 1.
16. RE for starting with 1 having zero or multiple even 1’s.
17. Regular Expression for multiple a’s and multiple b’s.
18. RE for exactly single 1 many 0’s |exactly single a many b.
19. A regular expression for strings starting with aa and ending with ba.
20. A regular expression for the language of all consecutive even length a’s.
21. A regular expression for the language of all odd-length strings
22. A regular expression for the language of all even length strings but ends
with aa.
23. A regular expression for the language of an odd number of 1s.
24. A regular expression for the language of even length strings starting
with a and ending with b in theory of automata.
25. A regular expression for the language of all even length strings but
starts with a.
26. A Regular Expression for the Language of all strings with an even
number of 0’s or even number of 1’s.
27. A regular expression for the language of all those strings end with abb.
28. A regular expression for string having must 010 or 101.
29. Regular expression of strings begin with 110
Regular expression of strings begin and end with 110
Regular expression of strings containing exactly three consecutive 1’s.
30. A Regular Expression of all strings divisible by 4.
31. A Regular Expression Strings that does not contain substring
110.
32. Regular expressions for all strings with at least one a
33. Regular expressions for all strings with at least two a’s
34. Regular expressions for All strings with exactly two b
35. Regular expressions for at least one a and at least one b
36. Regular expression form end in a double letter (two a’s or two b’s)
37. Regular expression for All strings containing exactly one a
 Tutorial No 2 Date:29/01/25

Chapter-2 Finite Automata

Draw a DFA for the language accepting strings ending with ‘0’ over input
alphabets ∑={0, 1} ?

Example 2: Draw a DFA for the language accepting strings ending with ‘01’
over input alphabets ∑={0, 1}

3: Draw a DFA for the language accepting strings ending with ‘00’ over
input alphabets ∑={0, 1} ?

Example 4: Draw a DFA for the language accepting strings ending with
‘011’ over input alphabets ∑ = {0, 1} ?

Example 5: Draw a DFA for the language accepting strings ending with
‘0110’ over input alphabets ∑ = {0, 1} ?

Example 6: Draw a DFA for the language accepting strings ending with
‘0011’ over input alphabets ∑ = {0, 1} ?

Example 7: Draw a DFA for the language accepting strings with ‘0’ only
over input alphabets ∑={0, 1} ?

Example 8: Draw a DFA for the language accepting strings with ‘0’ and ‘1’
only over input alphabets ∑={0, 1} ?

Example 9: Draw a DFA for the language accepting strings starting with ‘0’
over input alphabets ∑={0, 1} ?

Example 10: Draw a DFA for the language accepting strings starting with
‘01’ over input alphabets ∑={0, 1} ?

Example 11: Draw a DFA for the language accepting strings starting with
‘00’ over input alphabets ∑={0, 1} ?
Example 12: Draw a DFA for the language accepting strings starting with
‘011’ over input alphabets ∑ = {0, 1} ?

Example 13: Draw a DFA for the language accepting strings starting with
‘0110’ over input alphabets ∑ = {0, 1} ?

Example 14: Draw a DFA for the language accepting strings starting with
‘0011’ over input alphabets ∑ = {0, 1} ?

example 15: Draw a DFA for the language accepting strings starting with
‘00’ or ’11’ over input alphabets ∑ = {0, 1} ?

Example 16: Draw a DFA for the language accepting strings without
substring ‘00’ over input alphabets ∑ = {0, 1} ?

Example 17: Draw a DFA for the language accepting even binary numbers
strings over input alphabets ∑ = {0, 1} ?

Example 18: Draw a DFA for the language accepting odd binary numbers
strings over input alphabets ∑ = {0, 1} ?

Example 19: Draw a DFA for the language accepting odd or even binary
numbers strings over input alphabets ∑ = {0, 1} ?

Example 20: Draw a DFA for the language accepting strings containg even
number of total zeros over input alphabets ∑ = {0, 1} ?

Example 21: Draw a DFA for the language accepting strings starting and
ending with different characters over input alphabets ∑ = {0, 1} ?

Example 22: Draw a DFA for the language accepting strings starting and
ending with same character over input alphabets ∑ = {0, 1} ?

Example 23: Draw a DFA for the language accepting strings starting and
ending with ‘0’ always over input alphabets ∑ = {0, 1} ?
Example 24: Draw a DFA for the language accepting strings containing
three consecutives ‘0’ always over input alphabets ∑ = {0, 1} ?

Example 25: Draw a DFA for the language accepting strings such that each
‘0’ is immediately preceded and followed by ‘1’ over input alphabets ∑ = {0,
1} ?

Example 26: Draw a DFA for the language accepting strings containing at
most two ‘0’ over input alphabets ∑ = {0, 1} ?

Example 27: Draw a DFA for the language accepting strings containing at
least two ‘0’ over input alphabets ∑ = {0, 1} ?

Example 28: Draw a DFA for the language accepting strings containing
exactly two ‘0’ over input alphabets ∑ = {0, 1} ?

Example 29: Draw a DFA for the language accepting strings with ‘011’ as
substring over input alphabets ∑ = {0, 1} ?

Example 30: Draw a DFA for the language accepting strings ending in
either ’01’, or ’10’ over input alphabets ∑ = {0, 1} ?

Example 31: Draw a DFA for the language accepting strings containing
’01’, or ’10’ as substring over input alphabets ∑ = {0, 1} ?

Example 32: Draw DFA that accepts any string which ends with 1 or it ends
with an even number of 0’s following the last 1. Alphabets are {0,1}.

Example 33: Construct DFA accepting set of all strings containing even no.
of a’s and even no. of b’s over input alphabet {a,b}.

Example 34: Give DFA accepting the language over alphabet {0,1} such
that all strings of 0 and 1 ending in 101.

.
Example 35: construct DFA for binary integer divisible by 3 ?
Example 36: Construct a DFA that accepts a language L over input
alphabets ∑ = {a, b} such that L is the set of all strings starting with ‘aa’ or
‘bb’.

Example 37:Construct a DFA that accepts a language L over input

Ex 38:DFA for the language of all those strings starting and ending with the
same letters.

EX 39:DFA for the language of all those strings starting and ending with
different letters.

EX 40:DFA for the language of all those strings having double 0 or double 1.

EX:41 DFA for the language of all those strings starting and ending with b.

EX:42 DFA for ending with b.

EX 43:DFA for the string of even A’s and even b’s.