Recursive definition of a String

[DantesInferno]

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.

[diabolo]

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

[douglasm]

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.

[freakish777]

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."

[Yakk]

Spoiler:

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.

[Jplus]

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

[diabolo]

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"?

[Jplus]

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.

[DantesInferno]

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.

[Yakk]

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

[DantesInferno]

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

[Xanthir]

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. ^_^

[troyp]

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.)