Consider the grammar
->
->
-> aa
-> epsilon
-> b
-> aa
-> epsilon
Show that the language L() is equal to all strings of a's and b's with an even number of a's. You will need to show that every string generated by the grammar has an even number of a's and that every string with an even number of a's can be generated by the grammar. To show that every string generated by the grammar has an even number of a's, use induction on the number of rule applications. To show that every string with an even number of a's can be generated by the grammar, use induction on the length of the string.
Mathematics Homework Solutions
#28274
Context Free Grammar Problem
Please see attached...sorry looks to be an html problem.
What is this?
By OTA - Overall OTA Rating
Departed OTA
Purchase Cost Now
$2.19 CAD (was ~$15.96)
Included in Download
- Plain text response
- Attached file(s):
- 28274.pdf
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- Discrete Math - Discrete Math. See attached file for full problem description.
- Grammar Induction - Consider the grammar
1)
-> |epsilon 2) -> 0|1|2|3|4|5|6|7|8|9 Use induction to show that the number of strings in L( ) of length n is equal to 10^ ... - Context-fee language - Thank you for taking the time to look at my problem. I cannot make math symbols, thus, I will let ^ denote "raised to the power." For example, a^2 is a squared or a "raised to the power" of 2. Also, I ...
- Descrete Math multiple choice - Note: Please see attachment for full details. 3. A grammar that has no restrictions on production is called a: A) phrase-structure grammar. B) context-sensitive grammar. C) context-free gr ...
- Discrete Mathematics and Its Applications - Key Characteristics: Please give an English text description - in your own words - highlighting key characteristics of the topic. 1. Alphabet (or vocabulary): 2. Language: 3. Type 0 grammar: 4. ...
