CS/ECE 374 A (Spring 2022) Homework 4 (due Feb 17 Thursday at 10am)
Instructions: As in previous homeworks.
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}
Copyright By PowCoder代写 加微信 powcoder
(b) {0i1j0k :i+kisdivisibleby3,andkisdivisiblebyj,andi,j,k≥1}
(c) {yxxRz : x,y,z ∈ {0,1}∗, |x| ≥ 374} (d) {y0n1n0nz:y,z∈{0,1}∗, n≥374}
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}
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com