Wednesday, June 24, 2020

#31 For each of the following CFGs: (1) determine..

ChemistryExplain is here for you to provide the important questions and answer “#31 For each of the following CFGs: (1) determine which of the strings e, abba. aaaaa, and b is generated..” this question is coming from  Computer Science.
#31 For each of the following CFGs: (1) determine..
Get the Free Online Chemistry Q&A Questions And Answers with explain. To crack any examinations and Interview tests these Chemistry Questions And Answers are very useful. Here we have uploaded the Free Online Chemistry Questions. Here we are also given the all chemistry topic.

ChemistryExplain team has covered all Topics related to inorganic, organic, physical chemistry, and others So, Prepare these Chemistry Questions and Answers with Explanation Pdf.

Question


#31 For each of the following CFGs: (1) determine which of the strings e, abba. aaaaa, and b is generated, and (2) give an English description of the language.
#31 For each of the following CFGs (1) determine..

Answer


a) It denotes the set of all the strings containing only 'a' and 'b'.


S\rightarrow \epsilon
S\rightarrow aS\rightarrow a(bS) \rightarrow ab(bS) \rightarrow abb(a) \rightarrow abba
S\rightarrow aS\rightarrow a(aS) \rightarrow aa(aS) \rightarrow aaa(aS) \rightarrow aaaa(a) \rightarrow aaaaa
S\rightarrow b

b) It denotes the set of all the strings containing only 'a' and 'b' with three consecutive a at some point.

S cannot have \epsilon

S cannot have abba


S \rightarrow X(aaa)X \rightarrow (aX)aaa(X) \rightarrow (a\epsilon)aaa(X)\rightarrow aaaa(aX)\rightarrow aaaa(a\epsilon)\rightarrow aaaaa

S cannot have b

c) It denotes the set of all strings made up of only "a" with lengths 1, or 3 or more.

S doesn't have \epsilon

S doesn't have abba


S \rightarrow (aaS) \rightarrow aa(aaS) \rightarrow aaaa(a) \rightarrow aaaaa

S doesn't have b

d) It denotes the set of all strings of non zero length which have 0 or more 'b' followed by 0 or more 'a'

S doesn't have \epsilon

S doesn't have abba


S \rightarrow (aX) \rightarrow a(aX)\rightarrow aa(aX) \rightarrow aaa(aX) \rightarrow aaaa(a) \rightarrow aaaaa
S \rightarrow b

Labels:

posted by ChemistryExplain @ June 24, 2020   0 Comments

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home