关键词 > 4200/C语言代写
4200 - Formal Languages: Final Exam Spring 2021
发布时间：2022-12-06
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
4200 - Formal Languages: Final Exam
Spring 2021
Problem 1
20 points
Provide a regular expression α such that L(α) = A where A is the following language: A = Σ* _ {01}
where the alphabet Σ = {0, 1}.
Hint: One approach is to write down a DFA or an NFA that recognizes the language A first (in your scratch paper). And then, construct a regular expression that is equivalent to that DFA/NFA.
Answer: The steps (in scratch paper) are:
1. Write down a DFA that recognizes {01} language.
2. Swap the accept and reject states to create a DFA that recognizes A = Σ* _ {01}.
3. Look at transitions in the above DFA, and write down the regular expression accordingly. Final answer:
α = e u (0 u 11)(0 u 1)* u 10(0 u 1)(0 u 1)*
Problem 2
10 points
Write down a context-free grammar for the following language E . Please use S as the start variable. B = { 1z 0z _y l x > y > 0 }
Answer:
S - 1S l 1S0 l ∈ (2)
Problem 3
20 points
Given a language C = {1z 1y 025+1 l x, y, z > 0 and x = y}. Please answer the following questions:
1. Is the above language regular or non-regular? If Yes, provide a regular expression that recognizes C . Answer: Regular. Regular expression: (11)* (00)* 0.
2. Is the above language context-free or not? If Yes, provide a context-free grammar that generates C . Answer: Context-free.
S - AB0
A - 11A l e
B - 00B l e
3. Is the above language Turing-decidable or not?
Answer: Yes. Because any context-free language is also a Turing-decidable language.
4. Is the above language Turing-recognizable or not?
Answer: Yes. Because any context-free language is also Turing-recognizable language.
Problem 4
5 points
A and B are both regular languages, would A u B always be regular? Provide 1-3 sentences explaining your answer (i.e. why or why not).
Answer: Yes, AuB would always be regular because regular languages are closed under the Union operation.
Problem 5
5 points
A is a regular language and B is a non-regular language, would A u B always be non-regular? Please provide an example (or counterexample) to support your answer.
Answer: No. For example, if A = {0, 1}* , i.e., the set of all possible strings, and B is any non-regular language, then A u B = A. And because {0, 1}* is regular, then in this case, A u B is regular.
Problem 6
5 points
A is regular language and B is a non-context-free language, would A n B always be non-context-free? Please provide an example (or counterexample) to support your answer.
Answer: No. For example, if A = 0, i.e., the empty set, and B is a context-free language, then A n B = A = 0. Because 0 is a regular language, then in this case, A n B is a regular language, which by definition is also context-free.
