Knowee
Questions
Features
Study Tools

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.

🧐 Not the exact question you are looking for?Go ask a question

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:

  1. S -> aaa | bbb | aSa | bSb | ε

Here is a step-by-step explanation:

  1. The non-terminal symbol S represents a string whose length is a multiple of three.
  2. The production rule S -> aaa generates a string of three a's.
  3. The production rule S -> bbb generates a string of three b's.
  4. 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.
  5. 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.
  6. 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.

This problem has been solved

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.

1/1

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.