A grammar G generating language L is defined by:
G = ( {x,y}, {S,A,B,C}, P, S)
where the elements of P are:
S -> ABA
AB -> AC
CB -> BBC
CA -> BBA
A -> a | E
B -> b
Is the language L generated by G most accurately said to be:
A. Chomsky type 0
B. Chomsky type 1 (context sensitive)
C. Chomsky type 2 (context free)
D. Chomsky type 3 (regular)
E. None of the above
I think this is type 0 because it is not context sensitive. But I wonder this rules might be reduced to something else and becomes context sensitive or context free or so on. How to deal with this kind of question?
Grammar G is defined by:
G = ({a,b}, {S,A,B}, P, S)
where P is the set:
S -> AB | AS
A -> a | aA
B -> b | bb
Is the language L generated by G most accurately said to be:
A. Chomsky type 0
B. Chomsky type 1 (context sensitive)
C. Chomsky type 2 (context free)
D. Chomsky type 3 (regular)
E. None of the above
I think this is context free because LHS has one nonterminal. But I'm not sure because this rules might be reduced and becomes regular grammer..
Grammar 1 is context-sensitive as written (unsure why you think it's not, as it matches the formal definition unambiguously). Grammar 2 is context-free as written.
Grammar 1's language looks to be (a|E)b^k(a|E) where k is in the form 2^i, i is a non-negative integer. This language appears to be context-sensitive.
Grammar 2's language looks to be aa*(b|bb), which is regular.
Since the questions are asking about the languages, not the grammars as written, I would say that 1 is context-sensitive and 2 is regular.