1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Two computational theory language questions - multi choice

  1. Aug 7, 2017 #1
    1. The problem statement, all variables and given/known data
    ##1)## Which one of the following is an example of a set ##S## such that the language ##S^*## has the same number of 8-letter words as 4-letter words?
    1) ##S = \{aaaa \quad bbbb\}##
    2) ##S = \{bbbb \quad bbbbbb\}##
    3) ##S = \{aa \quad bb\}##
    4) ##S = \{a \quad bbbb\}##

    ##2)## Consider the language NOTABandEVEN over ##\{a \quad b\}## consisting of all words of even length that do not contain the substring ##ab##. Which one of the following is a suitable generator?
    1) ##baa##
    2) ##bbbaab##
    3) ##ba##
    4) ##babb##



    2. Relevant equations
    None.

    3. The attempt at a solution
    In the first question we can easily eliminate 3 and 4. 1 has two possibilities for both four-letter and eight-letter words. 2 has one possibility for each, so we have two correct answers. Or have I overlooked something?

    In the second question all of the given strings result in words containing the forbidden substring. The only possibility I see is option 3 with the only word generated being ##ba##, so the language in question consists of only one word. Correct?
     
  2. jcsd
  3. Aug 7, 2017 #2

    jedishrfu

    Staff: Mentor

  4. Aug 7, 2017 #3
    For question 1, choice 1, I get 4 8-letter words, and only 2 4-letter words.

    It's not clear what is meant by generator in question 2. Generally a language is generated by a grammar, or a set of production rules. The meaning here seems to be like a generator for a group: ab, generates {∅, ab, abab, abababab, .....}. The problems is that any string with one or more a 's and one or more b's in it will fail, and you won't generate the entire language anyway. something like this is needed:
    S→BA
    A→aA
    B→bB
    A→∅
    B→∅
    ∅ is the empty string
     
  5. Aug 8, 2017 #4
    The question seems to limit one to words resulting from concatenating the given strings so I assume ##bbaa## and ##bbbaaa## do not qualify. Quite frankly I feel both questions are a bit vague.
     
  6. Aug 8, 2017 #5
    Okay, I can see that now. I neglected the possibilities of all ##a## and all ##b##. As for the term "generator" in question 2, I agree that it is far from clear and one has to assume what it requires.
     
  7. Aug 8, 2017 #6
    Thanks for the input.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Two computational theory language questions - multi choice
Loading...