Sunday, 23 June 2013

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