Results 1 to 2 of 2

Thread: Need Help With Formal Language Theory

  1. #1
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Question Need Help With Formal Language Theory

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,240
    Thanks
    2835

    Re: Need Help With Formal Language Theory

    Quote Originally Posted by marsandfruit View Post
    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 by HallsofIvy; Jun 22nd 2017 at 12:03 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Mar 17th 2013, 02:38 AM
  2. language of mathematics
    Posted in the Math Forum
    Replies: 1
    Last Post: Nov 10th 2011, 12:09 AM
  3. How to write this in formal language
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 21st 2011, 04:45 PM
  4. set theory / predicate logic math language problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 7th 2010, 12:21 AM

Search Tags


/mathhelpforum @mathhelpforum