Introduction to Recursive Definitions in The Theory of Computation
Explore recursive definitions in the realm of computation theory through examples like defining sets of even numbers, factorial language, palindrome strings, and more. Learn how to prove properties using recursive rules and construct languages with specific patterns and constraints.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The Theory of Computation - 3 - Recursive Definition / .
Recursive Definition Recursive Definition : . . . 1 2 . . 3 .
:Even Numbers . 2 : : : 2n n= 1 2 3 4 . : : Rule1: 2 is even. Rule2: if x is in EVEN, then it is x+2 . Rule3: The only elements in the set Even are that can be produced from the two rules above.
Example1: By using all the definitions above, prove that 14 is EVEN. . 7 = 2 14 . 2n : . 1 14 . 2 14= 2 * 7 14
By Rule1: we know that 2 is even. By Rule2: We know that 2+2=4 4+2=6 6+2=8 8+2=10 10+2=12 12+2=14 So 14 is Even.
Example2: Defining the language factorial Step 1: As 0!=1, so 1 is in factorial. Step 2: n!=n*(n-1)! is in factorial. Step 3: No strings except those constructed in above, are allowed to be in factorial. Example3: Defining the language PALINDROME, defined over = {a,b} Step 1: a and b are in PALINDROME Step 2:if x is palindrome, then s(x)Rev(s) and xx will also be palindrome, where s belongs to * Step 3:No strings except those constructed in above, are allowed to be in palindrome
Example4: Defining the language {anbn }, n=1,2,3,... , of strings defined over ={a,b} Step 1: ab is in {anbn} Step 2: if x is in {anbn}, then axb is in {anbn} Step 3: No strings except those constructed in above, are allowed to be in {anbn} Example5: Defining the language L, of strings ending in a , defined over ={a,b} Step 1: a is in L Step 2: if x is in L then s(x) is also in L, where s belongs to * Step 3: No strings except those constructed in above, are allowed to be in L
Example6: Defining the language L, of strings containing exactly one a, defined over ={a, b} Step 1: a is in L Step 2:s(aa)s is also in L, where s belongs to b* Step 3: No strings except those constructed in above, are allowed to be in L Example7: Defining the language L,of strings beginning and ending in same letters , defined over ={a, b} Step 1: a and b are in L Step 2:(a)s(a) and (b)s(b) are also in L, where s belongs to * Step 3:No strings except those constructed in above, are allowed to be in L
Example8: Defining the language L, of strings containing aa or bb , defined over ={a, b} Step 1: aa and bb are in L Step 2:s(aa)s and s(bb)s are also in L, where s belongs to * Step 3: No strings except those constructed in above, are allowed to be in L
H.W By using definition1, definition2, and recursive definition: Prove that 11 is ODD. Rule1: 2 is even. Rule2: if x is in EVEN, then it is x+2 . Rule3: The only elements in the set Even are that can be produced from the two rules above.
