Obtain grammar to generate strings of a’s and b’s such that string length is multiple of three.
Question
Obtain grammar to generate strings of a’s and b’s such that string length is multiple of three.
Solution
Sure, here is a context-free grammar that generates strings of a's and b's such that the string length is a multiple of three:
- S -> aaa | bbb | aSa | bSb | ε
Here is a step-by-step explanation:
- The non-terminal symbol S represents a string whose length is a multiple of three.
- The production rule S -> aaa generates a string of three a's.
- The production rule S -> bbb generates a string of three b's.
- The production rule S -> aSa generates a string whose length is a multiple of three, by adding an 'a' at the beginning and end of any string generated by S.
- The production rule S -> bSb generates a string whose length is a multiple of three, by adding a 'b' at the beginning and end of any string generated by S.
- The production rule S -> ε generates an empty string, which has a length of zero (a multiple of three).
This grammar can generate all strings of a's and b's whose length is a multiple of three, and only those strings.
Similar Questions
Which regular grammar generates the language consisting of strings with zero or more occurrences of "a" followed by "b"? Options : S -> ab | aS | ε S -> a | b | aS S -> ab | aS none
Give a regular expression for all strings whose length is strictly greater than 3.
// write a method to find length of string and write 3 test cases
For the following language over Σ = {a, b}, provide a regular expression and a DFA for the language. Your automata should have at most 10 states.The set of strings that contain exactly three as and an even number of bs. For example, abababb is in the language, while ababab is not.
For the language over Σ = {a, b}, provide a regular expression and a DFA for the language. Your automata should have at most 10 states.The set of strings that contain exactly three as and an even number of bs. For example, abababb is in the language, while ababab is not.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.