CODEWITHSUNDEEP
recursiondefinitionsautomata-theorykleene-star
Faizan Saleem
Faizan Saleem

Reputation: 41

Need help about recursive definition for two languages S* and T* where S={aa,b} and T={w1,w2,w3,w4}

I am currently taking a course of Theory of Automata and i came up with following problems. I came up with the answer of 1st one but confused about the statement of 2nd question.

(i) Give a recursive definition for the language S* where S = {aa,b}.

Step 1: Lamba, aa, b are in S.

Step 2: If x is in S then so is bx and xb.

I want to confirm my confirm my answer.

And the following the question i am totally confused about and isn't able to come up with an answer.

(ii) Give a recursive definition for the language T* where T = {w1, w2, w3, w4} where these w's are some particular words.

Upvotes: 1

Views: 1133

Answers (2)

Shadow Lynx
Shadow Lynx

Reputation: 1

I think your answer is a little wrong as, you have declared x = lambda,aa and b and in step 2 you have written that "bx are in language S" which would be wrong because if x =b then the answer would be "bb" which is not included in the language

so I think that correct answer of step 2 will be if w ∈ S* then waa is also in Language S

Upvotes: 0

Patrick87
Patrick87

Reputation: 28292

(i) Very close. You are missing at least one rule, and you have one rule which is not needed. You need either xaa or aax in step 2. You need only one of the rules you give in step 2, not both. Otherwise this is right. A minimal recursive definition is:

  1. lambda is in S
  2. if x is in S, then aax and bx are in S.

(ii) Same as (i), just generalized. Answer is

  1. lambda is in T
  2. if x is in T, then w1x, w2x, w3x, w4x are in T.

Upvotes: 0

Related Questions