Regular Expression and Finite Automata

Describe the language denoted by the following regular expressions:

a) a(a|b)*a

The expression denotes the set of all strings of length two or more that start and end with an ‘a’.

b) ((e|a)b*)*

The expression denotes the set of all strings over the alphabet {a,b}.

c) (a|b)*a(a|b)(a|b)

The expression denotes the set of all strings of length 3 or more with an ‘a’ in the third position from the right. Ie of form yaxz where y is an arbitrary string , and x and z are single characters.

d) a*ba*ba*ba*

The expression denotes the set of all strings that contain precisely 3 b’s.

e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*

The expression denotes the set of all strings of even length.

True or False

1. In a finite language no string is pumpable. True
2. A DFA has infinite number of states. False
3. A DFA can have more than one accepting state. True
4. In DFA all states have same number of transitions. True
5. Every subset of a regular language is regular. False
6. Let L4 = L1L2L3. If L1 and L2 are regular and L3 is not regular, it is possible that L4 is regular. True
7. In a finite language no string is pumpable. True
8. If A is a nonregular language, then A must be infinite. True
9. Every context-free language has a context-free grammarin Chomsky normal form. True
10. If A is a context-free language, then A must be nonregular. False
11. The class of regular languages is closed under intersection. True
12. If a language A is regular, then it A must be finite. False
13. Every language is Turing-recognizable. False
14. If a language is context-free, then it must be Turing-decidable. True
15. The problem of determining if a context-free grammar generates
    the empty language is undecidable. False
16. The problem of determining if a Turing machine recognizes the
    empty language is undecidable. True
17. The set of all languages over an alphabet is countable.False
18. There are some languages recognized by a 5-tape, nondetermin-
    istic Turing machine that cannot be recognized by a 1-tape,
    deterministic Turing machine.False
    
19. The language { 0n1n | 0 ≤ n ≤ 1000 } is regular. True
20. Nonregular languages are recognized by NFAs. False
21. The class of context-free languages is closed under intersection. False
22. A language has a regular expression if and only if it
    has an NFA. True
23. The regular expression (01*0 ∪ 1)*0 generates the language
    consisting of all strings over {0, 1} having
    an odd number of 0’s. False
24. If a language A has a PDA, then A is generated by a
    context-free grammar in Chomsky normal form. True
25. If A is a context-free language and B is a language such that B is a subset of A, then B must be a context-free language. False
26. If a language A has an NFA, then A is nonregular. False
27. The regular expressions (a ∪ b)* and (b*a*)* generate the same language. True
28. If a language A has a regular expression, then it also has a context-free grammar. True