Question

Let Σ= {a, b}. Give recursive definitions for the following languages over Σ.

The language NOTBB of all words not containing the substring bb

Answer 1

The language NOTBB can be recursively defined using an empty string and a set of rules that allow adding 'a' or 'b' to the existing string without forming the 'bb' substring. The definition includes base cases and construction rules that prevent the inclusion of the prohibited substring.

Step-by-step explanation:

To provide a recursive definition for the language NOTBB which consists of all words over the alphabet Σ = {a, b} that do not contain the substring 'bb', we can define the language as follows:

• 
  
• Base case: The empty string ε is in NOTBB.
• 
  
• The letter 'a' by itself is in NOTBB.
• 
  
• If 'x' is a string in NOTBB, so is 'xa' (since adding 'a' to any string which doesn’t contain 'bb' will not produce 'bb').
• 
  
• If 'x' is a string in NOTBB that does not end in 'b', then 'xb' is also in NOTBB (appending 'b' to a string that does not contain 'bb' nor ends in 'b' does not create the substring 'bb').
• 
  
• No string ending in 'bb' can be included in NOTBB.

Essentially, this recursive definition allows the construction of strings while carefully avoiding the creation of the 'bb' substring, step by step. Any string formed using these rules will be in the language NOTBB.