Regular & context-free grammar problem

[m***@email.com]

Let A and B be two sets of words (strings) from S*, for some alphabet
of symbols S. Suppose that B is a
subset of A. Which of the following statements must always be true of A
and B ?
I. If A is finite, then B is finite.
II. If A is regular, then B is regular.
III. If A is context-free, then B is context-free.

The answer key gives the answer "I. only".

II. I thought this statement is true because a regular grammar is
restricted to rules from some set of forms. (see
http://en.wikipedia.org/wiki/Regular_grammar). Thus, any subset of a
regular grammar will still have rules restricted to that set of forms.

III. I don't see how taking a subset of a grammar can cause it to have
context.

Why are II and III wrong? Thanks

[tuncay tekle]

Post by m***@email.com
Which of the following statements must always be true of A
and B ?
I. If A is finite, then B is finite.
II. If A is regular, then B is regular.
III. If A is context-free, then B is context-free.

II and III can easily be proven wrong with the same counter-example.

II is wrong: Suppose A = (a|b|...)* where (a|b|...) goes on for all
letters in Sigma and Sigma is the input alphabet, then obviously it
contains all possible strings over Sigma and is regular. But there are
many subsets of A that are not regular (basically any irregular
language over Sigma is a subset of A).

III is also wrong: Suppose A is defined by the rules:

S -> aS | bS | .... | epsilon

where epsilon is the empty string and it goes to every letter followed
by S. A is the set of all possible strings over Sigma again, and is
context-free. But there are many subsets of A that are not context-free
(basically any non-context-free language over Sigma is a subset of A).

[m***@email.com]

Post by tuncay tekle

Post by m***@email.com
Which of the following statements must always be true of A
and B ?
I. If A is finite, then B is finite.
II. If A is regular, then B is regular.
III. If A is context-free, then B is context-free.

II and III can easily be proven wrong with the same counter-example.
II is wrong: Suppose A = (a|b|...)* where (a|b|...) goes on for all
letters in Sigma and Sigma is the input alphabet, then obviously it
contains all possible strings over Sigma and is regular. But there are
many subsets of A that are not regular (basically any irregular
language over Sigma is a subset of A).

How can a set of words be regular? I thought only grammars can be
regular, and there can be multiple grammars for a given set of words.
Furthermore, it seems to me that given a set of words like S* =
{a,b,...}*, it is always possible to create a regular grammar which can
create any word in the language, for example S -> aS, S -> bS, ..., S
-> epsilon.

Could you give a simple example of a non-regular set of words and a
non-context-free set of words?

Thanks

[tuncay tekle]

Post by m***@email.com
How can a set of words be regular? I thought only grammars can be
regular, and there can be multiple grammars for a given set of words.

A regular language is one that is recognized by a DFA (deterministic
finite acceptor) or equivalently can be written as a regular
expression. Has nothing to do with grammars.

Post by m***@email.com
Furthermore, it seems to me that given a set of words like S* =
{a,b,...}*, it is always possible to create a regular grammar which can
create any word in the language, for example S -> aS, S -> bS, ..., S
-> epsilon.

Yes it's true that any regular language is also context-free, but not
the other way around.

Post by m***@email.com
Could you give a simple example of a non-regular set of words and a
non-context-free set of words?

Generally an example of an irregular language is a^n b^n (ie the set
{epsilon,ab,aabb,aaabbb,...} ), in other words, when there's infinite
counting related within itself, regular expressions cannot capture
this. Notice that this language is indeed context-free:

S -> aSb | epsilon

recognizes this language.

A non-context-free language is weirdly enough a^n b^n c^n (ie the set
{epsilon,abc,aabbcc,...} ). The problem with this language is that you
depend on multiple character counting, which is easy to show that you
cannot put into Greibach normal form, hence is not context-free.

[Till Crueger]

How can a set of words be regular? I thought only grammars can be regular,
and there can be multiple grammars for a given set of words. Furthermore,
it seems to me that given a set of words like S* = {a,b,...}*, it is
always possible to create a regular grammar which can create any word in
the language, for example S -> aS, S -> bS, ..., S -> epsilon.

Quite easy. A set of words S is regular if there exists a regular grammar
G with S = L(G) i.e. S is the language described by G. Same holds for
context free grammars and others.

Note that the existence of a non regular gramar does not make a language
non regular.

HTH,
Till

[Michal Nazarewicz]

Post by m***@email.com
Could you give a simple example of a non-regular set of words

A set of word with n letters 'a' followed by exactly n letters 'b',
ie. generated by grammar: S -> a S b | epsilon.

Post by m***@email.com
and a non-context-free set of words?

A set of words with n letters 'a' followed by exactly n letters 'b'
followed by exactly n letters 'c'.

[Barb Knox]

Post by m***@email.com
Let A and B be two sets of words (strings) from S*, for some alphabet
of symbols S. Suppose that B is a
subset of A. Which of the following statements must always be true of A
and B ?
I. If A is finite, then B is finite.
II. If A is regular, then B is regular.
III. If A is context-free, then B is context-free.
The answer key gives the answer "I. only".
II. I thought this statement is true because a regular grammar is
restricted to rules from some set of forms. (see
http://en.wikipedia.org/wiki/Regular_grammar). Thus, any subset of a
regular grammar will still have rules restricted to that set of forms.
III. I don't see how taking a subset of a grammar can cause it to have
context.
Why are II and III wrong? Thanks

You're thinking of taking a subset of the grammar RULES for a language,
but the question refers to taking a subset of the generated STRINGS of a
language. These are two different beasties.

[Michal Nazarewicz]

Post by m***@email.com
Let A and B be two sets of words (strings) from S*, for some alphabet
of symbols S. Suppose that B is a
subset of A. Which of the following statements must always be true of A
and B ?
I. If A is finite, then B is finite.

This is clearly true.

Post by m***@email.com
II. If A is regular, then B is regular.

Consider a regular grammar:
start -> empty
start -> 'a' start
start -> 'b' start
ie. word containing letters 'a' and 'b'. Let A be a set of all words
generated by those rules.

And now consider context-free grammar:
start -> empty
start -> 'a' start 'b'
ie. string containing letters 'a' followed by the same number of
letters 'b'. Let B be a set of all words generated by those rules.

Clearly, B is a subset of A however "B grammar" is not a regular
grammar.

Post by m***@email.com
III. If A is context-free, then B is context-free.

There's probably similar example but I cannot think of any at the
moment.

BTW. Note that I may be wrong here.

/* Followup-To set to comp.theory */