Question

Question 1: Every language is regular

T/F

Question 2: There exists a DFA that has only one final state

T/F

Question 3: Let M be a DFA, and define flip(M) as the DFA which is identical to M except you flip that final state. Then for every M, the language L(M)^c (complement) = L( flip (M)).

T/F

Question 4: Let G be a right linear grammar, and reverse(G)=reverse of G, i.e. if G has a rule A -> w B fir variables A,B and strings w, then reverse(G) has a rule A -> B w^R

There exists a right linear grammar G such that L(G) = L(reverse(G))

T/F

Question 5:

Let RL be the set of two regular languages. To prove RL is closed under intersection, it is equivalent to prove that “There exists two regular languages L1L2 such that L1 intersect L2 is also regular.”

T/F

Question 6: You can assume that L={a^n b^n : n >=0} is not regular.

For every regular language L', L union L' is not regular.

T/F

Question 7: Any NFA can be turned into an equivalent NFA that has two final states.

T/F

Question 8: A DFA M accepts string w if there exists an accepting path from the initial state to a final state when talking the input W.

T/F

Question 9: The language L = {(ab)^n : n >= 0} is equal to the language L' = {a^n b^n: n >=0}.

T/F

Question 10: You can assume that the set of regular languages is closed under homomorphism, i.e. every homomorphic mapping. Suppose you have a homomorphic mapping h, and h(L) is regular. We can conclude that L is regular.

T/F

Question 11: Any regular grammar G can be turned into a DFA M such that L(G) = L(M)

T/F

Answer 1

Answer 1 :True, simply because every language accepted by an NFA is regular, and every regular language is context-free.

Answer 2: True,there exists DFA with 1 final state. Some but not all DFA's require more than 1 final states, so by restricting DFA with only one final state which may require more than one final state will not accept the language it should accept. So DFA with one final state is less powerful than DFA with more than one final state.

Answer 3:True

Answer 4:False

Answer 5: True

Answer 6:True, if L is Non regular then for any regular language L' , L union L' is not regular .

Answer 7:False

Answer 8:True
Answer 9:True

Answer 10:True:using algorithm ,if you have a homomorphic mapping h, and h(L) is regular therefore l is regular

Answer 11: True: Using the algorithm, any DFA may be converted to a regular grammar