28. Let ? {a,b), and let L be the language over ? exactly consisting of all stri
ID: 3915441 • Letter: 2
Question
28. Let ? {a,b), and let L be the language over ? exactly consisting of all strings that do not contain the substring aaa. Consider the following regular expressions: (ii) (b + ab + aab)"(A + a + aa) (iii) (A + + aa)(b + ba-baa)" Which of the following is correct? (a) Only regular expression (i) generates L (b) Only regular expressionii generates L (c) Only regular expression (ii) generates L (d) Only regular expressions (i) and) generate L (e) Only regular expressions (i) andi) generate L (f) Only regular expressions (ii) and ) generate L (g) All 3 regular expressions generate L (h) None of the 3 regular expressions generates L 2.9. Let ?-{a,b), and let L-(antra": n > 1, w E ?*). Consider the following statements: (i) L has regular expression ?*(a + b)"a" (ii) L is a non-regular language. (ii) L has context-free grammar where S, X are non terminals (iv) L has context-free grammar where S,X are nonterminals. Which of the following is true? (a) Only statement (i) is correct. (b) Only statement (ii is correct (c) Only statement is correct (d) Only statement (iv) is correct. (e) Only statements (i) and iii are correct (f) Only statements (i) and (iv) are correct. (g) Only statementsi) and iii) are correct. (h) Only statements and (iv) are correct (i) Only statements (ii), and (iv) are correct (i) All the 4 statements are correct. (k) None of the 4 statements is correct.Explanation / Answer
2.8.
Regular expression(i) generate strings consists of substring “aaa”
It produces language L={^, a, aaa,baaab, aaaabb…} so (i) Is false
The regular expressions (ii) and (iii) will produce strings that do not contain
the substring”aaa”
Answer is option(f)
2.9
(i) is incorrect because it can produce zero or more a’s followed with any substring or null string and ends with zero ormore a’s.
(II)is correct its not a regular language
iii) it can produce a S a
a aS a
a abS a
a abaa a Doesn’t belong to language L
iV. S-> aSa
a aXa a
aa aX aa
aa abX aa It produces an w an
Answer is option H
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.