Another recursive math question

73 Views Asked by At

Given the alphabet {def ghi}, give a recursive definition for the language whose words contain the string defdef.

My solution is:

i) def ∈ L and ghi ∈ L

ii) if u = def and w ∈ L*, then so is uu, wuu, uuw, wwuu, uuww, wuuw

My question is that I feel like I need to keep adding parts to L* or do I stop at wuuw ?

1

There are 1 best solutions below

4
On BEST ANSWER

A little introduction in 'How to solve these types of questions': Your first rule should contain the simplest words in the language that can be used as a root to construct all the other words. In the question given this is 'defdef'. 'defdef' is the minimal word that fulfills the constraint: "word w has to contain 'defdef' ".

Afterwards you try to build every other possible word from the words you chose for Rule i).

If it is not possible to contruct every other word from Rule i) then you have to add more roots to Rule i). For an example of this review my answer to your last question.

Rule i) $$defdef \in L$$

Rule ii) $$ w\in L \Rightarrow defw \in L \land wdef \in L \land ghiw \in L \land wghi \in L $$