Homework Sourse13 Which of the following is untrue about DFA A Each state e
13. Which of the following is untrue about DFA?
A. Each state emits one labeled edge for each letter of alphabet A
B. There may not be any final states
C. There must be at least a final state
D. One state is designated as the start state
15. Which of the following languages is not a regular language?
A.
{, a, b, aa, bb, aaa, bbb, …, an, bn, …}
B.
{, ab, aabb, aaabbb, …, anbn, …}
C.
{, ab, abab, ababab, …, (ab)n, …}
D.
B and C above
16. What is the right regular expression for strings whose length is multiple of 3 over the alphabet {a, b}?
A.
((a + b)( a + b)(a + b))*
B.
(aaa + bbb)*
C.
(aaa)* + (bbb)*
D.
(a + b)*
17. What is the right regular expression that describes the following language? {^, a, b, c, aa, bb, cc, …, an, bn, cn, …}
A.
a + b + c
B.
a*b*c*
C.
a* + b* + c*
D.
+ a + b + c
18. Which of the following grammars is a left regular grammar?
A.
S -> aSb | ba
B.
S -> Sab | ab
C.
S -> abS | ab
D.
S -> SSa | b
| A. | {, a, b, aa, bb, aaa, bbb, …, an, bn, …} | |
| B. | {, ab, aabb, aaabbb, …, anbn, …} | |
| C. | {, ab, abab, ababab, …, (ab)n, …} | |
| D. | B and C above |
Solution
13. B There may not be any final states. It is untrue because in DFA onre state is start state and a set of states may be final states.
16. D (a+b)*
