0. Introduction. A grammar is a set of rules for generating strings. For this project, you will write a Python program that generates random strings using the rules of a grammar. For example, when the program was given the strings of a grammar, it generated the following random sentences. the cat bit the dog. the girl chased the boy the cat chased the boy and the boy kissed the cat . the cat bit the dog and the dog kissed the girl and the dog chased the girl . Perhaps such grammars could write children's books automatically. Seriously, however, more complex grammars have been used to generate random test inputs for programs, as a debugging 1. Theor To write this program, you must have a way to generate random integers. You must also know what a grammar is, and how it works Random integers. No algorithm can generate truly random integers, but it can generate pseudo-random integers that seem random, even though they're not. Python has its own random number generators, but for this project, you must implement your own. The Park-Miller algorithm (named for its inventors) is a simple way to generate a sequence of pseudo-random integer terms. It works like this. Let N, be an integer called the seed. The seed is the first term of the sequence, and must be between 1 and 2 2, inclusive. Starting from the seed, later terms N, N are produced by the following equation. Nk+,-(75M) % (231-1) Here 7 is 16807, and 2" is 2147483648. The Python operator& returns the remainder after dividing one integer by another. You always get the same sequence of terms from a given seed For example, if you start with the seed 101, then you get a pseudo-random sequence whose first few terms are 1697507, 612712738, 67890020 695061696, 1738368639, 246698238 1613847356, and 1214050682. Terms in the sequence may be large, but you can make them smaller by using the s operator again. If N is a term from the sequence, then N % M gives you an integer between 0 and M-1, inclusive. For example, if you need an integer between 0 and 9, then you write N 10. You can use this to choose a random element from a Python list or tuple. If S is the list or tuple, then the Python expression StN& len(S)] returns a randomly chosen element of S. Grammars. The easiest way to explain a grammar is to show an example. This is the grammar that generated the simple sentences about boys, cats, dogs, and girls that appeared in the introduction. 01 Noun ,eat 04 Noum.girl 06 Erb ,chased, 07 Rrb.kissed. 08 F%-ase 'the. Noun vb ,the. Noun 09StoryPhrase 10 Story. Phrase .and.Sion. 11 Slart Story 0. Introduction. A grammar is a set of rules for generating strings. For this project, you will write a Python program that generates random strings using the rules of a grammar. For example, when the program was given the strings of a grammar, it generated the following random sentences. the cat bit the dog. the girl chased the boy the cat chased the boy and the boy kissed the cat . the cat bit the dog and the dog kissed the girl and the dog chased the girl . Perhaps such grammars could write children's books automatically. Seriously, however, more complex grammars have been used to generate random test inputs for programs, as a debugging 1. Theor To write this program, you must have a way to generate random integers. You must also know what a grammar is, and how it works Random integers. No algorithm can generate truly random integers, but it can generate pseudo-random integers that seem random, even though they're not. Python has its own random number generators, but for this project, you must implement your own. The Park-Miller algorithm (named for its inventors) is a simple way to generate a sequence of pseudo-random integer terms. It works like this. Let N, be an integer called the seed. The seed is the first term of the sequence, and must be between 1 and 2 2, inclusive. Starting from the seed, later terms N, N are produced by the following equation. Nk+,-(75M) % (231-1) Here 7 is 16807, and 2" is 2147483648. The Python operator& returns the remainder after dividing one integer by another. You always get the same sequence of terms from a given seed For example, if you start with the seed 101, then you get a pseudo-random sequence whose first few terms are 1697507, 612712738, 67890020 695061696, 1738368639, 246698238 1613847356, and 1214050682. Terms in the sequence may be large, but you can make them smaller by using the s operator again. If N is a term from the sequence, then N % M gives you an integer between 0 and M-1, inclusive. For example, if you need an integer between 0 and 9, then you write N 10. You can use this to choose a random element from a Python list or tuple. If S is the list or tuple, then the Python expression StN& len(S)] returns a randomly chosen element of S. Grammars. The easiest way to explain a grammar is to show an example. This is the grammar that generated the simple sentences about boys, cats, dogs, and girls that appeared in the introduction. 01 Noun ,eat 04 Noum.girl 06 Erb ,chased, 07 Rrb.kissed. 08 F%-ase 'the. Noun vb ,the. Noun 09StoryPhrase 10 Story. Phrase .and.Sion. 11 Slart Story