CS402 Midterm Quiz 1 May 2023 by Miss Mehwish

Q1. While finding RE corresponding to TG, if TG has more than one start state, then what action should be taken?

1. Replace the old final state with the new start state
2. Eliminate the old start state
3. Introduce the new start state
4. Replace the old start state with the final state

Correct option: b) Eliminate the old start state

Q2. An FA is a collection of:

1. Finite states, finite transitions, and finite input letters
2. Infinite states, infinite transitions, and infinite input letters
3. Only infinite states and infinite transitions
4. Only finite states and finite transitions

Correct option: a) Finite states, finite transitions, and finite input letters

Q3. If S = {a}, then which option correctly represents S multiplied by {a, aaa, aaaaa, aaaaaaa,...}?

1. S{a, aaa, aaaaa, aaaaaaa,...}
2. {aa, aaaa, aaaaaa, aaaaaaaa,...}
3. {a, aaa, aaaa, aaaaa,...}
4. {a, aa, aaa, aaaa,...}

Correct option: a) S{a, aaa, aaaaa, aaaaaaa,...}

Q4. An FA of the EVEN-EVEN language shows that it accepts the null string by declaring the _________ as an _________ as well.

1. Final state, initial state
2. Final state, null state
3. Initial state, null state
4. Initial state, final state

Correct option: a) Final state, initial state

Q5. Which statement is false about the PALINDROME LANGUAGE?

1. An FA can be built for it.
2. Every word is the reverse of itself.
3. It is an infinite language.
4. None of the given options.

Correct option: b) Every word is the reverse of itself.

Q6. In an FA, when there is no path from the initial state to the final state, then that FA _____________.

1. Accepts all strings.
2. Does not accept any string.
3. Accepts all non-empty strings.
4. None of the given options.

Correct option: b) Does not accept any string.

Q7. Which one of the following words is not accepted by the given regular expression: (a+b)*(aaa+bbb)(a+b)*ab?

1. abab
2. baaaa
3. bbbb
4. ababaaaab

Correct option: c) bbbb

Q8. If we have the regular expression (a+b)*(aaa + bbb)(a+b)*, then we can draw a TG for the provided RE with a minimum number of _________ state(s).

1. 0
2. 1
3. 2
4. 3

Correct option: c) 2