COMP-330A Introduction to Computability
COMP 330A 2019, Assignment 3 Due Thursday, November 7th 2019 23:59
[10%]
[8%] [10%]
[10%] [8%]
[8%] [8%]
[8%]
COMP-330A Introduction to Computability
2.999 Let ∑ = { 0,1,∪,∘,*,(,),ø,€ }
( We used the euro sign “€” for the empty string to distinguish it from the empty string itself “𝞮”,i.e. |𝞮|=0 while |€|=1 ).
Define LREG = { w∈∑* | w is a valid REGULAR EXPRESSION }.
[10%] a. Show LREG ∉ REG [10%] b. Show LREG ∈ CFL
Let ∑ = { 0,1,A,B,…,Y,Z,(,),⟪,⟫,{,},⇨,€, ❜}
( We used the euro sign “€” for the empty string to distinguish it from the empty
string itself “𝞮”,i.e. |𝞮|=0 while |€|=1, the special comma sign “❜” to distinguish it
from the normal comma “,” , the brackets “⟪,⟫” to distinguish them from the normal brackets “⟨,⟩” and the special arrow “⇨” to distinguish it from the normal “→”).
Define LCFG = { w∈∑* | w is a valid Context-Free Grammar in implicit form }.
c. Show LCFG ∈ CFL. HINT: the first rules of your grammar should be something like
[10%]
⟨CFG⟩➞{⟨RULES⟩} ⟨RULES⟩➞⟨RULE⟩ | ⟨RULE⟩❜⟨RULES⟩
⟨RULE⟩➞ ⟪ ⟨NAME⟩ ⟫ ⇨ ⟨STRING⟩ …
COMP-330A Introduction to Computability
€ acts as 𝞮 in the alphabet above to avoid confusion.
A context-free grammar is in implicit form if it is only an R. The set V is extracted from R as every sub-string of the form ⟨ {A,B,…,Z}+ ⟩ such as ⟨VAR⟩, or ⟨EXPRESSION⟩. The terminals are simply {0,1}, and the start variable is the leftmost part of the first rule of R.
Examples of valid strings in LCFG are
(the grammar G1 of page 102) {⟪A⟫⇨0⟪A⟫1❜⟪A⟫⇨⟪B⟫❜⟪B⟫⇨#}
(the grammar of example 2.3) {⟪S⟫⇨0⟪S⟫1❜⟪S⟫⇨⟪S⟫⟪S⟫❜⟪S⟫⇨€}