Recursive definition of a String

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

DantesInferno
Posts: 5
Joined: Tue Jan 18, 2011 11:13 pm UTC

Recursive definition of a String

Postby DantesInferno » Wed Mar 28, 2012 10:53 am UTC

Hey all,

Today I had a test for my Algorithms and Data Structures course and one questions has been bugging the hell out of me. I tried talking to the lecturer after and I still wasn't able to understand what he was asking or what he was expecting in the answer. I have since googled the problem to no avail. When I attempted to question my friends on Facebook, I got answers such as "I have legs." which reminded me most of my FB friends are idiots.

Which leads me to here. I hoping one of you guys will be able to shed some light on the problem, which is as follows.

Given that a string is a concatenation of characters, the following is an (incomplete) recursive definition of a string:
"Concatenation of a string and a character is a string."
a) What is missing?
b) Write the complete definition.

I "think" I have determined that the base case is missing. But why that is or how I write it in the definition, I'm lost.

User avatar
diabolo
Posts: 72
Joined: Fri Aug 08, 2008 4:17 pm UTC
Location: france

Re: Recursive definition of a String

Postby diabolo » Wed Mar 28, 2012 11:27 am UTC

I'd say you need to be able to have an empty string so you can concatenate the first character.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: Recursive definition of a String

Postby douglasm » Wed Mar 28, 2012 6:25 pm UTC

You are correct that the missing detail is the base case. As written, the definition is completely self-referential and impossible to use to determine whether anything is a string or not. diabolo is correct that the required base case is the empty string.

User avatar
freakish777
Posts: 354
Joined: Wed Jul 13, 2011 2:14 pm UTC

Re: Recursive definition of a String

Postby freakish777 » Wed Mar 28, 2012 6:53 pm UTC

Are they looking for the definition add to the existing sentence or to add another sentence as well?

If the latter, you'll want to expand the following to cover all combinations:

"Concatenation of a string and a string is a string."
"Concatenation of a string and a character is a string."
"Concatenation of a string and an empty string is a string."

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Recursive definition of a String

Postby Yakk » Wed Mar 28, 2012 7:48 pm UTC

Spoiler:
DantesInferno wrote:Hey all,

Today I had a test for my Algorithms and Data Structures course and one questions has been bugging the hell out of me. I tried talking to the lecturer after and I still wasn't able to understand what he was asking or what he was expecting in the answer. I have since googled the problem to no avail. When I attempted to question my friends on Facebook, I got answers such as "I have legs." which reminded me most of my FB friends are idiots.

Which leads me to here. I hoping one of you guys will be able to shed some light on the problem, which is as follows.

Given that a string is a concatenation of characters, the following is an (incomplete) recursive definition of a string:
"Concatenation of a string and a character is a string."
a) What is missing?
b) Write the complete definition.

I "think" I have determined that the base case is missing. But why that is or how I write it in the definition, I'm lost.

The empty string is a string. Concatenation of a string and a character is a string.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Recursive definition of a String

Postby Jplus » Wed Mar 28, 2012 7:52 pm UTC

Make that "a sequence of zero characters is a string". And then the recursive part.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
diabolo
Posts: 72
Joined: Fri Aug 08, 2008 4:17 pm UTC
Location: france

Re: Recursive definition of a String

Postby diabolo » Thu Mar 29, 2012 7:34 am UTC

Jplus wrote:Make that "a sequence of zero characters is a string". And then the recursive part.

Wouldn't the definition of "sequence" already cover the recursive part (eg. "the empty sequence or a concatenation of a sequence and an element")?
If you're going to use this term to define a string couldn't you just say "a sequence of [zero or more] characters is a string"?

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Recursive definition of a String

Postby Jplus » Thu Mar 29, 2012 7:43 am UTC

Yeah perhaps you should leave "sequence" out. In that case, either define how the absence of any character is enough to call it a string (without calling it an "empty string" straight away), or use some kind of special terminal symbol.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

DantesInferno
Posts: 5
Joined: Tue Jan 18, 2011 11:13 pm UTC

Re: Recursive definition of a String

Postby DantesInferno » Sat Mar 31, 2012 3:12 am UTC

I talked to my lecturer and discovered the answer.

The base case is definitely missing and the base case is that a lone character is counted as a string.

Makes less sense than some of the stuff mentioned in this thread, but that's apparently what he was expecting.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Recursive definition of a String

Postby Yakk » Sat Mar 31, 2012 4:38 am UTC

Hmm? Zero characters isn't a string? How Fortran of the lecturer.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

DantesInferno
Posts: 5
Joined: Tue Jan 18, 2011 11:13 pm UTC

Re: Recursive definition of a String

Postby DantesInferno » Sat Mar 31, 2012 12:02 pm UTC

Yakk wrote:Hmm? Zero characters isn't a string? How Fortran of the lecturer.


Funny that you say that, the lecturer actually had a big (Off-topic) discussion about the development of programming languages and how he's been there since the beginning. He gave great emphasis on his time as a FORTRAN programmer :P

User avatar
Xanthir
My HERO!!!
Posts: 5423
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Recursive definition of a String

Postby Xanthir » Sun Apr 01, 2012 7:51 pm UTC

Well, your lecturer's preferred answer is valid, but it doesn't match the definition of "string" in virtually any programming language (except FORTRAN I guess). So maybe don't learn that answer from him. ^_^
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Recursive definition of a String

Postby troyp » Tue Apr 03, 2012 8:43 pm UTC

Hadn't they invented empty strings back then? Maybe one day we'll invent negative strings and then we'll need a third clause to the recursive definition.

(Actually negative strings would come in handy sometimes, especially when you've got string operators. But I guess it'd be a bad idea to unify string concatenation and string difference when you'd be corrupting the "always succeeds" aspect of concatenation. Maybe you could have different datatypes, strings and signed strings where the former are automatically cast to the latter, like a mini numerical-tower.)


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 8 guests