DFA Problems automata theory and for.pptx

Dfa problems in ATFL

1. Construct DFA [FINITE LANGUAGE]

2. Construct DFA(Finite Number of Strings ) L = { a }, Σ = {a} L = { aa }, Σ = {a} L = { ab, baa }, Σ = {a, b} L = { ab, a }, Σ = {a, b} L = { a n / n=0 or 3 or 5 }, Σ = {a}

3. L = { a m b n / 1<=m, n<=2 }, Σ = {a, b} L = { a m b n / m+n =2 }, Σ = {a, b} L = { w ε Σ * / |w|=2 }, Σ = {a, b} L = { w ε Σ * / |w|<=2 }, Σ = {a, b} L = { w ε Σ * / w= w R ,|w|=3 }, Σ = {a, b}

4. 1 . L = { a }, Σ = {a}

5. 2 . L = { aa }, Σ = {a}

6. 3. L = { ab, baa }, Σ = {a, b }

7. 4. L = { ab, a }, Σ = {a, b }

8. 5. L = { a n / n=0 or 3 or 5 }, Σ = {a}

9. L = { a m b n / 1<=m, n<=2 }, Σ = {a, b}

10. 7. L = { a m b n / m+n =2 }, Σ = {a, b}

11. 8. L = { w ε Σ * / |w|=2 }, Σ = {a, b }

12. 9. L = { w ε Σ * / |w|<=2 }, Σ = {a, b}

13. 10. L = { w ε Σ * / w= w R ,|w|=3 }, Σ = {a, b}

14. Construct DFA [INFINATE LANGUAGE ]

15. Construct a DFA that accept all the strings of 1’s and 0’s that every string start with 10 010

16. Construct a DFA that accept all the strings of 1’s and 0’s that every string end with 10 010

17. Construct a DFA that accept all the strings of 1’s and 0’s that every substring contains 01 100 0101

18. 4 . Construct a DFA that Start with 1 and end with 0 over an alphabet Σ = {0, 1} Start with 11 and end with 00 over an alphabet Σ = {0, 1}

19. 5. Design a DFA that accept the language consists of set of strings that is Odd number of 0’s over an alphabet Σ = {0, 1} Even number of 1’s over an alphabet Σ = {0, 1}

20. Design a DFA that accept the language consists of set of strings that is Even number of 0’s and even number of 1’s over an alphabet Σ = {0, 1} Even number of 0’s and odd number of 1’s over an alphabet Σ = {0, 1} c) odd number of 0’s and even number of 1’s over an alphabet Σ = {0, 1} d) odd number of 0’s and odd number of 1’s over an alphabet Σ = {0, 1}

21. Design a DFA that accept the language consists of set of strings over an alphabet Σ = {0, 1} 0’s divisible by 3 and 1’s divisible by 2 0’s divisible by 2 and 1’s divisible by 4 0’s divisible by 5 and 1’s divisible by 3

22. 8. Design a DFA that accept the language consists of set of strings ( Σ = {0, 1}) Divisible by 2 ( 0(mod 2)) Divisible by 3 ( 0(mod 3)) Divisible by 5 ( 0(mod 5)) 3(mod 6) 4(mod 7) 7(mod 256)

23. Construct a DFA that accept all strings of 1’s and 0’s every string contains the substring Dibit Tribit

24. 10 . Construct a DFA that accept the strings of 1’s and 0’s where The second symbol from left end is 1 The 3 rd symbol from right end is 0

25. 11. Construct a DFA, Σ = {0, 1} String with next to last symbol is 0 String with next to last symbol is 1

26. 12. Design a DFA that accept the language consists of set of strings that is any number of 0’s followed by any number of 1’s over an alphabet Σ = {0, 1} any number of 0’s followed by any number of 1’s followed by any numbers of 2’s over an alphabet Σ = {0, 1, 2} any number of 0’s followed by any number of 1’s followed by any numbers of 2’s followed by any number of 3’s over an alphabet Σ = {0, 1, 2, 3} At least one ‘a’ followed by at least one ‘b’ followed by at least one ‘c’ over an alphabet Σ = { a, b, c }

27. Construct a DFA that accept all the strings of a’s and b’s where every string start with a whose length= divisible by 3 ab whose length= 2(mod 4) bab whose length= 1(mod 5)

28. 14. construct a DFA that accept all the strings of 1’s and 0’s Every string start and end with 0 Every string start and end with same symbol Every string start and end with different symbol

29. 15. Construct DFA , Σ = {a} L = { a n / n>=0, n!=3 }, L = { a n / n>=0, n!=2, n!=4 }

30. 16.Construct A DFA that accept all the strings of a’s and b’s where each string contains Exactly Two a’s At most Two a’s At least Two a’s