Give a recursive definition for the following languages: 1. L1 = { X3k+1 , k >=0

Question

Give a recursive definition for the following languages:


1. L1 = { X3k+1 , k >=0}
2. L2 = { odd Palindromes over {a,b,c} }
3. L3 = { all words over the alphabet {a,b} of odd length }
4. L4 = { all words over the alphabet {a,b} containing substring bbb }
5. L5 = { xny3n+1 n = 1,2,….}

Sample solution

L1 = { Xeven}
L1 = { Xeven}={ , where is an empty string.
Rule 1: .
Rule 2: if W , so is WXX.
Rule 3: No other element is in .

Explanation / Answer

1) Assuming strings must have length 3k+1 where k>= 0 L1 = { Rule1: X is in L1 Rule 2: IF W then WXXX, XWXX, XXWX, XXXW There are no other rules } 2) L2 ={ Rule1: empty string(e) is in L2 Rule2: a, b, c are in L2 Rule3: IF W then aWa, bWb, cWc There are no other rules } 3) L3 = {Rule1: a, b are in L3 Rule2: If W then aaW, aWa, Waa, abW, aWb, Wab, baW, bWa, Wba, bbW, bWb, Wbb There are no other rules } 4) L4 = {Rule1: bbb is in L4 Rule2: If W then aW, Wa, bW, Wb there are no other rules } 5) assuming strings have number of x's equal to n and number of y's equal to 3n+1 L5 ={ Rule1: xyyyy is in L5 Rule2: if W then xWyyy There are no other rules }

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.