Let F denote some finite language, R denote some regular language, C denote some

Question

Let F denote some finite language, R denote some regular language, C denote some context-free language, D denote some decidable language, E denote some recognizable language, and N denote some non-recognizable language. For each of the following statements, prove whether it always holds, sometimes holds, or never holds:

a) RN is regular
Holds: always / sometimes / never
proof:

b) N - R is regular
Holds: always / sometimes / never
proof:

c) N (opposite sign of U) F is not regular
Holds: always / sometimes / never
proof:

d) N - F is regular
Holds: always / sometimes / never
proof:

e) C* is infinite
Holds: always / sometimes / never
proof:

f) R is context- free
Holds: always / sometimes / never
proof:

Explanation / Answer

a)      RN is regular
Solution: never
proof: Here, N is non-recognizable language and R is regular Language. Every Regular language is designed by DFA. But, Every Non-Recognizable language is not designed by DFA. Hence, RN is never can be DFA. Thus, RN can be never regular.

b)      N - R is regular
Solution: sometimes
proof: When Regular language is get subtracted from the Non-recognizable Language then sometimes the result is regular and sometimes it is not regular. It depends upon only the given Languages problem.

c)      N (opposite sign of U) F is not regular
Solution: sometimes
proof: N (opposite sign of U) F is finite, and a finite language could be regular or could not be regular. Thus,   N (opposite sign of U) F is sometimes not regular.

d)      N - F is regular
Solution: sometimes
proof: When finite language is get subtracted from the Non-recognizable Language then sometimes the result is regular and sometimes it is not regular. It depends upon only the given Languages problem.

e)      C* is infinite
Solution: always
proof: As per the Kleene Closure property, if any Language L is context-free then its Kleene Closure will also be context free. C* is infinite, as due to Kleene’s Property, context-free grammar becomes infinite. Thus, C* is always infinite.

f)       R is context- free
Solution: always
proof: Every regular grammar is context-free but it is not necessary that every context-free grammar will be regular. Thus, R means Regular language will always be context-free.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.