Need Help With Formal Language Theory

Jun 2017
25
1
San Diego
I need some assistance with this formal language theory problem.

2. (5 points) When defining a formal language, we usually name our alphabet Σ. Consider a language that has the following alphabet:
Σ = {a, b, e}

A language that belongs to this alphabet is a set of strings that are all made up of the symbols of the alphabet. For examples, the set L = {aab, abe, be} is a valid language defined over this
alphabet because all of its strings are made of symbols that exist in Σ. Now answer the following questions:

Write five strings that are valid strings in the given alphabet.
Write three languages that are valid languages defined over the given alphabet.
Write a string that is not a valid string for the given alphabet.
How many strings of length 2 can be made given this alphabet?
For defining a language, instead of giving the full set of the strings that are accepted in
it (the way L was defined above) you can also describe the properties of its members in simple English. For example, you can define a language by saying “the language that accepts/has all the strings that are composed of an a followed by an even number of f ’s ” (notice that this example language has an infinite number of strings). Now, using simple English give three languages defined over Σ that have an infinite number of strings.
 

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
I need some assistance with this formal language theory problem.

2. (5 points) When defining a formal language, we usually name our alphabet Σ. Consider a language that has the following alphabet:
Σ = {a, b, e}
Was it really {a, b, e} rather than {a, b, c}? No reason it can't be but that seems peculiar!

A language that belongs to this alphabet is a set of strings that are all made up of the symbols of the alphabet. For examples, the set L = {aab, abe, be} is a valid language defined over this
alphabet because all of its strings are made of symbols that exist in Σ. Now answer the following questions:

Write five strings that are valid strings in the given alphabet.
Didn't you just write how to do this? Just give any 5 strings that are made up only of the letters "a", "b", or "e". "aaaa", "ab", "be" are three such strings. Write two more such strings

Write three languages that are valid languages defined over the given alphabet.
A "language" over an alphabet is any set of such strings.

Write a string that is not a valid string for the given alphabet.
"abc" is such a string. "123" is another. Do you see why? Can you give an another example?

How many strings of length 2 can be made given this alphabet?
There are 3 choices for the first letter and 3 choices for the second so 3*3= 9 such strings. It is not hard to write them all: aa, ab, ac, ba, bb, bc, ca, cb, cc.

For defining a language, instead of giving the full set of the strings that are accepted in
it (the way L was defined above) you can also describe the properties of its members in simple English. For example, you can define a language by saying “the language that accepts/has all the strings that are composed of an a followed by an even number of f ’s ” (notice that this example language has an infinite number of strings). Now, using simple English give three languages defined over Σ that have an infinite number of strings.
"All strings that contain the substring 'abc' " is one example. Surely you can write two more.
 
Last edited: