Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Consider the following grammar (given in Chomsky normal form): SAB ABS | b BSA | a a. The shortest string generated by this grammar is ba. The shortest strings not generated by this grammar are €, a, and b. Give the next two shortest strings generated by this grammar, and two other short strings not generated by this grammar. b. Draw the parse tree given this grammar for the string bbaaba. c. Find a long path -- eg, with 5 nonterminals -- from the root to a leaf in your parse tree. Starting at the bottom of that path, find the first nonterminal that appears twice along the path. Circle the two occurrences of the repeated nonterminal, and draw an outline around the subtree generated by the lower occurrence and an outline around the subtree generated by the upper occurrence. In accordance with the Pumping Lemma for the CFLs and given the string z = bbaaba, what are the values of the 5 substrings U, V, W, X, Y determined by the subtrees you have indicated? Be sure to give a value (even if just €) for each of the 5 variables.

Consider the following grammar (given in Chomsky normal form): SAB ABS | b BSA | a a. The shortest string generated by this grammar is ba. The shortest strings not generated by this grammar are €, a, and b. Give the next two shortest strings generated by this grammar, and two other short strings not generated by this grammar. b. Draw the parse tree given this grammar for the string bbaaba. c. Find a long path -- eg, with 5 nonterminals -- from the root to a leaf in your parse tree. Starting at the bottom of that path, find the first nonterminal that appears twice along the path. Circle the two occurrences of the repeated nonterminal, and draw an outline around the subtree generated by the lower occurrence and an outline around the subtree generated by the upper occurrence. In accordance with the Pumping Lemma for the CFLs and given the string z = bbaaba, what are the values of the 5 substrings U, V, W, X, Y determined by the subtrees you have indicated? Be sure to give a value (even if just €) for each of the 5 variables.

C++ Programming: From Problem Analysis to Program Design
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter18: Stacks And Queues
Section: Chapter Questions
Problem 35SA
See similar textbooks
icon
Related questions
Question

Can you help me solve this problem? 

Consider the following grammar (given in Chomsky normal form): SAB ABS | b BSA | a a. The shortest string generated by this grammar is ba. The shortest strings not generated by this grammar are €, a, and b. Give the next two shortest strings generated by this grammar, and two other short strings not generated by this grammar. b. Draw the parse tree given this grammar for the string bbaaba. c. Find a long path -- eg, with 5 nonterminals -- from the root to a leaf in your parse tree. Starting at the bottom of that path, find the first nonterminal that appears twice along the path. Circle the two occurrences of the repeated nonterminal, and draw an outline around the subtree generated by the lower occurrence and an outline around the subtree generated by the upper occurrence. In accordance with the Pumping Lemma for the CFLs and given the string z = bbaaba, what are the values of the 5 substrings U, V, W, X, Y determined by the subtrees you have indicated? Be sure to give a value (even if just €) for each of the 5 variables.
Transcribed Image Text:Consider the following grammar (given in Chomsky normal form): SAB ABS | b BSA | a a. The shortest string generated by this grammar is ba. The shortest strings not generated by this grammar are €, a, and b. Give the next two shortest strings generated by this grammar, and two other short strings not generated by this grammar. b. Draw the parse tree given this grammar for the string bbaaba. c. Find a long path -- eg, with 5 nonterminals -- from the root to a leaf in your parse tree. Starting at the bottom of that path, find the first nonterminal that appears twice along the path. Circle the two occurrences of the repeated nonterminal, and draw an outline around the subtree generated by the lower occurrence and an outline around the subtree generated by the upper occurrence. In accordance with the Pumping Lemma for the CFLs and given the string z = bbaaba, what are the values of the 5 substrings U, V, W, X, Y determined by the subtrees you have indicated? Be sure to give a value (even if just €) for each of the 5 variables.
Expert Solution
steps

Step by step

Solved in 2 steps with 2 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ for Engineers and Scientists
C++ for Engineers and Scientists
Computer Science
ISBN:
9781133187844
Author:
Bronson, Gary J.
Publisher:
Course Technology Ptr
CMPTR
CMPTR
Computer Science
ISBN:
9781337681872
Author:
PINARD
Publisher:
Cengage
Systems Architecture
Systems Architecture
Computer Science
ISBN:
9781305080195
Author:
Stephen D. Burd
Publisher:
Cengage Learning
Operations Research : Applications and Algorithms
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
Np Ms Office 365/Excel 2016 I Ntermed
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:
9781337508841
Author:
Carey
Publisher:
Cengage
SEE MORE TEXTBOOKS