CS/ECE 374 A (Spring 2022) Homework 4 Solutions
Problem 4.1: For each of the following languages, determine whether it is regular or not, and give a proof. To prove that a language is not regular, you should use the fooling set method. (To prove that a language is regular, you are allowed to use known facts about regular languages, e.g., closure properties, all finite languages are regular, . . . )
(a) {x(110)nxR :x∈{0,1}∗, n≥1}
(b) {0i1j0k :i+kisdivisibleby3,andkisdivisiblebyj,andi,j,k≥1}
Copyright By PowCoder代写 加微信 powcoder
(c) {yxxRz : x,y,z ∈ {0,1}∗, |x| ≥ 374} (d) {y0n1n0nz:y,z∈{0,1}∗, n≥374}
Solution: In each of the parts below, let L be the language in question.
(a) We prove that L is not regular by the fooling set method. ChooseF ={0i :i≥0}.
Let x and y be two arbitrary distinct strings in F. Thenx=0i andy=0j forsomei̸=j.
Choose z = 110 · 0i.
Thenxz=0i·110·0i =0i·110·(0i)R ∈L.
On the other hand, yz = 0i ·110·0j ̸∈ L, because i ̸= j (in more detail: yz has only one occurrence of a substring of the form (110)n with n ≥ 1, and that substring has n = 1; the part before the substring is 0i and the part after the substring is 0j, but 0i ̸= (0j)R if i ̸= j).
Thus, F is a fooling set.
Since F is infinite, L cannot be regular.
(b) We prove that L is not regular by the fooling set method.
Choose F = {013n−1 : n ≥ 1}.
Let x and y be two arbitrary distinct strings in F.
Thenx=013m−1 andy=013n−1 forsomem,n≥1withm̸=n. Withoutlossof generality, assume m < n (the other case is symmetric).
Choose z = 03m−1.
Then xz = 013m−103m−1 ∈ L, since 1+(3m−1) = 3m is divisible by 3 and 3m−1 is divisible by 3m − 1.
On the other hand, yz = 013n−103m−1 ̸∈ L, because 3m − 1 is not divisible by 3n − 1 since m < n.
Thus, F is a fooling set.
Since F is infinite, L cannot be regular.
[Note: F = {0n : n ≥ 1} won’t work here.]
(c) We prove that L is regular.
By definition, L consists of all strings that contain xxR as a substring for some string x
of length at least 374, i.e., all strings that contain an even-length palindrome of length at least 2 · 374 = 748.
Observe that if a string w contains an even-length palindrome of length at least 748, i.e., a substring of the form al ···a1 · a1 ···al with a1,...,al ∈ {0,1} and l ≥ 374, then it must contain a palindrome of length exactly 748, namely, a374 · · · a1 · a1 · · · a374.
Let A be the set of all palindromes of length exactly 748. Since A is finite, A is regular. Since L = (0 + 1)∗A(0 + 1)∗, we conclude that L is also regular.
(d) We prove that L is not regular by the fooling set method.
ChooseF ={0i :i≥374}.
Let x and y be two arbitrary distinct strings in F.
Then x = 0i and y = 0j for some i,j ≥ 374 with i ̸= j. Without loss of generality, assume i > j (the other case is symmetric).
Choose z = 1i0i.
Then xz = 0i1i0i ∈ L, since xz trivially contains 0i1i0i as a substring and i ≥ 374.
On the other hand, yz = 0j1i0i ̸∈ L by the following argument: if yz is in L, then it contains a substring of the form 0n1n0n for some n ≥ 374; then the middle block 1n must be equal to 1i, and so n = i; and the left block 0n must be contained in 0j, implying that i = n ≤ j, which contradicts the i > j assumption.
Thus, F is a fooling set.
Since F is infinite, L cannot be regular.
Problem 4.2: Give a context-free grammar (CFG) for each of the following languages. You must provide explanation for how your grammar works, by describing in English what is generated by each non-terminal. (Formal proofs of correctness are not required.)
(a) (30 pts) {x(110)nxR : x ∈ {0, 1}∗, n ≥ 1} (b) (30pts) {1i0j1k :j=2i+3k, i,j,k≥0}
(c) (40pts) {1i0j1k :i+kisdivisibleby3and0≤j≤k} Solution:
S → 0S0|1S1|A A → 110A|110
Explanation:
A generates {(110)n : n ≥ 1}.
S generates {x(110)nxR : x ∈ {0, 1}∗}.
AC|1AC2|11AC1
000C0111 | 00C0111 | 0C0111 | C0111 | ε
000C1111 | 00C1111 | 0C1111 | C1111 | 01 | 1 000C2111 | 00C2111 | 0C2111 | C2111 | 0011 | 011 | 11
A0B0A0 | A0B1A2 | A0B2A1 | A1B0A2 | A1B1A1 | A1B2A0 | A2B0A1 | A2B1A0 | A2B2A2 111A0|ε
000B0 111 | ε 0B01 00B011
A → 1A00|ε B → 000B1|ε
Explanation:
A generates all strings of the form 1i02i (i ≥ 0).
B generates all strings of the form 03k1k (k ≥ 0).
S generates all strings of the form 1i02i ·03k1k = 1i0j1k with j = 2i+3k (i,k ≥ 0),
as desired. (c)
Explanation: Observe that L = {1i0j1k : i+k ≡ 0 mod 3, i ≥ 0, k ≥ j} = {1i·(0j1j)·1l : i+j+l≡0mod3, i,l≥0}.
for each p ∈ {0,1,2}: Ap generates all strings of the form 1i with i ≡ p mod 3.
for each q ∈ {0,1,2}: Bq generates all strings of the form 0j1j with j ≡ q mod 3.
S generates L = {1i ·(0j1j)·1l : i+j+l ≡ 0mod3, i,l ≥ 0}, since S goes to
ApBqAr overallcombinationsofp,q,r∈{0,1,2}withp+q+r≡0mod3. [Note: There are other equivalent solutions. For example:
Here, A generates all strings of the form 1i with i ≡ 0 mod 3, and Cp generates all strings oftheform0j1k withj≤kandk≡pmod3.]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com