0

Given the alphabet $A = \{a,b\}^*$ and function

$\operatorname{equals}(q,w) = \begin{cases} a, & \text{if } q = w \\ \epsilon, & \text{otherwise} \end{cases}$

How to define primitive recursive function to one above? Just the idea, without proofs will be sufficient for me.

Michael Hardy
  • 1
helloFromTheOtherSide
  • 3

1 Answers1

0

If both are empty strings, then they are the same.

If one is an empty string and the other one is not, they are not the same.

If they are both non-empty strings, but the first letter is different, then they are not the same.

If they are both non-empty, and their first letter is the same, then they are the same if what comes after that letter is the same for both ( so here is where you get the recursion!)

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • For regular recursion solution is easy, but I can't come up with idea when I have to use primitive recursion. – helloFromTheOtherSide Mar 20 '17 at 01:24
  • @helloFromTheOtherSide Hmmm, I know about primitive recursive functions as functions defied over the natiral numbers, but I am not familiar with primitive recursive functions in the context of languages ... How are they defined in that context? – Bram28 Mar 20 '17 at 01:27