---
Video Title: Warm-up: Questions about Strings
Description: Theory of Computation
https://uvatoc.github.io/week6

12.1: Warm-up: Questions about Strings
- What yes/no questions might we ask about a sting?

Nathan Brunelle and David Evans
University of Virginia
---


Your warm-up is basically
to think of some yes-no

question that you
could ask about a string.

For instance, one question
that I might ask about

a string is, is it at least
seven characters long?

Something like that.

Who can give me more yes-no questions that
we could ask about a string?

Yeah.

Does it have some character in it?

Or some character from a group of
characters or something like that?

Okay, what else?

Yeah.

Is there a character that is three times
in a row?

Okay, what else?

Yeah.

Is it empty?

Okay.

Is it finite?

Okay, what else?

Yeah.

Is it a palindrome?

That's a good one.

Yeah.

Okay, is it a digit?

It's like a number zero through nine or
something like that.

Or does it have a digit?

Something like that.

Other things?

Yes.

So does it have a finite alphabet?

Okay.

Yes.

Yeah, does it have a character or some
group of characters in it?

What else?

Other things?

Anything else?

You might want to ask about a string.

How about this one?

Is it a Java program?

That's a question we can ask about a
string.

I can hand you a string and say,
is this a valid Java program?

We need to do this a lot, don't we?

What do we call the things that answer
this question of, is it a Java program?

We have a special name for that.

Compiler.

Yeah, so compiler or interpreter
is the program that we have

that just answers this question
of, is it a Java program?

So when you compile Java, kind of the
first thing that it does is it says,

wait, was that even Java that you handed
me?

And if it was, if it didn't look like Java,
then it said, no, that's not valid Java.

And if it did look like Java, then it does
other stuff with it after that.

How about this?

Is it a Java program that will,
let's say, print high?

That's another one we could do.

Is it a Java program that will print high?

That's another question we could ask about
strings.

Yes?

Is it a Java program that will eventually
stop?

Yes, that's another good question that we
could ask about strings.

We oftentimes will ask this question of,
is this program going to stop?

Do I have any infinite loops in this
program?

Is it a good thing or a bad thing if we
have infinite loops?

It depends?

It depends on what?

On what you want it to do.

What's a situation where an infinite loop
is a bad thing?

What is one situation like that?

Maybe you're trying to do some arithmetic
or something like that.

You're trying to execute some arithmetic.

Probably you wanted to get an answer
eventually.

You didn't want it to get stuck in an
infinite loop somewhere.

Your 2150 homework.

Probably that's pretty
universally bad if your

2150 homework has an
infinite loop in it somewhere.

What's a situation where an infinite loop
is a good thing?

Yeah.

In a game?

Okay.

You want your game to never stop?

Okay.

Maybe it would be better
for your GPA if it did stop,

but bad for the bottom
line of the company, I guess.

Okay, so if you've got a program that's
maybe watching for updates on another

thing, so if you're trying to constantly,
I don't know, read weather reports or

something like that, then maybe you want
this to run forever, where it just

occasionally pings and says, any new
weather?

Yeah, so like your operating system might
be another thing.

In fact, you consider it an error when
your operating system halts.

When that program terminates, then that
was because something went wrong.

So operating systems, also something you
want to run an infinite loop, and so forth.

Sorry.

I wish there was an infinite loop,
and so forth.

You know God was sitting
down and painting systems

that appropriately,
ちょっとしゅうするのは...oubliaそうにしゅうあなたは