关键词 > 4200/C语言代写
4200 - Formal Languages: Final Exam Fall 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
Fall 2021
Problem 1
20 points
Provide a regular expression α such that L(α) = A where A is the following language:
A = { w e Σ* | each 1 in w is followed by exactly one or two 0’s } where the alphabet Σ = {0, 1}.
Answer:
Example strings in A:
A = {∈, 0, 00, 000, ...} n {1010, 10100, 001010, ...}
Regular expression: α = 0* (10 n 100)*
Note: This α = (0 n 10 n 100)* is wrong because it also matches strings e.g. 100000 which has more than two 0’s right after the 1.
Problem 2
20 points
Write down a context-free grammar for the following language B . Please use S as the start variable.
B = { 1x 0y | x, y > 1 and x is odd and y is even. }
Answer:
S → AB
A → 1 | 11A
B → 00 | 00B
(1)
(2)
(3)
Problem 3
30 points
Given a language C = {1x 0y 0z | x, y, z > 0 and z > x + y}. Please answer the following questions:
1. Is the above language regular or non-regular? (Yes/No)
· If Yes, provide a regular expression that recognizes C.
· If No, provide a proof using pumping lemma for Regular languages (following the style and format of proofs in the textbook).
Answer: No. Not regular.
Proof sketch:
· Counter example s = 1p 0p+1 e C (i.e., where x = p, y = p + 1, z = 0)
· Pumping up with i = 2 always yields a string containing more 1’s than 0’s i.e., contradicting the condition z > x + y . That is, because the substring y always contains 1’s (because |xy| < p), pumping up i = 2 always yields strings of the form 1k 0j where k > j and these strings are 
C.
· Note: given the above counterexample string, pumping down is a bad idea because it would still yield strings with more 0’s than 1’s and therefore the resultant strings are still e C (no contradiction).
2. Is the above language context-free or not? (Yes/No)
· If Yes, provide a context-free grammar that generates C.
· If No, provide a proof using pumping lemma for context-free languages (following the style and format of proofs in the textbook).
Answer: Yes. Context-free.
Intuitively, the condition for generating strings e C is only that the total number of 0’s must be more than the number of 1’s.
S → 1S0 | A
A → 0A
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 is a Turing-recognizable language. The complement of A, i.e., 
, is a regular language.
Would A be a Turing-decidable language? (Yes/No). Provide 1-3 sentences explaining your answer.
Answer: Yes. When both A and 
are Turing-recognizable, then A is Turing-decidable because it is possible to construct a TM that decides A using two TMs, one recognizing A and one recognizing 
.
Problem 5
5 points
Is {0, 1}* a countable set? (Yes/No). Provide 1-3 sentences explaining your answer.
Hint: In this language, the alphabet, here {0, 1}, is countable and the strings, by definition of the asterate operation (see L01-3 lecture) are of finite length.
Answer: Yes. The strings are of finite length, we can sort all the strings, first, by their length and then by alphabetical order in order to count them, i.e., to establish an one-to-one correspondence between this language and the natural set N .
Problem 6
5 points
Is the set of all possible binary numbers (which can be of infinite length) a countable set? (Yes/No). Provide 1-3 sentences explaining your answer.
Answer: No. Because the strings can be infinitely long and using the diagonalization method, one can prove that the set is uncountable.
Problem 7
5 points
C is a Turing-recognizable language and Σ * is a Turing-decidable language. Is 
= Σ* - C always Turing-
recognizable? (Yes/No). Provide 1-3 sentences explaining your answer.
Answer: No, not always.
By definition, Σ* is always Turing-decidable regardless of what C is. Here, we essentially only know that C is Turing-recognizable. Therefore its complement, i.e., 
, may or may not be Turing-recognizable.
