# Two computational theory language questions - multi choice

1. Aug 7, 2017

### Lord Anoobis

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. Aug 7, 2017

3. Aug 7, 2017

### willem2

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

4. Aug 8, 2017

### Lord Anoobis

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.

5. Aug 8, 2017

### Lord Anoobis

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.

6. Aug 8, 2017

### Lord Anoobis

Thanks for the input.