Grammar in Chomsky Normal Form
Not what you're looking for?
Let G be the grammar
S -> ASB | e
A -> aAS | a
B -> SbS | A |bb
"e" in first rule indicates Epsilon or empty string.
Put G into Chomsky normal form.
Purchase this Solution
Solution Summary
The expert examines Grammar in Chomsky Normal Form.
Solution Preview
1. Eliminate "S -> e" (empty string) rule, and add all the variants with S replaced by empty string.
S -> AB
A -> aA
B -> Sb
You can choose either of "B -> Sb" and "B -> bS".
This results in following modified grammar that does not generate empty string.
S -> ASB | AB
A -> aAS | aA | a
B -> SbS | Sb | A | bb
2. Eliminate the rule "B -> A" from above ruleset, and add all the variants with B replaced by A.
S -> ASA | AA
This ...
Purchase this Solution
Free BrainMass Quizzes
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.
C# variables and classes
This quiz contains questions about C# classes and variables.
C++ Operators
This quiz tests a student's knowledge about C++ operators.
Basic Networking Questions
This quiz consists of some basic networking questions.