Daksh Prashan (Questions) : Can you answer them.
1. If we limit length of tape of Turing Machine, what language exactly will it accept.
2. Language of pairs of CFGs descriptions, such that language of first grammar is equal to second. Sipser says it is not decidable.
1. If we limit length of tape of Turing Machine, what language exactly will it accept.
2. Language of pairs of CFGs descriptions, such that language of first grammar is equal to second. Sipser says it is not decidable.
But we can always convert two grammers in Chomsky Normal Form. And map every rule of first grammer with some suitable rule in second. We can think of this as follow:
1. Consider all terminals marked. Find one rule each from both grammars, having same RHS side. Now replace Non-terninal in second rule with non terminal of first. Replace it throughout the second grammar.
2. If we get some rule whose RHS have all non-terminals, that are replaced by non-terminals of first grammar, consider this rule to be checked for replacing non-terminal on LHS.
3. Repeat until no further rule can be mapped. Check if both grammars are exactly equal. If yes then accept otherwise reject.
No comments:
Post a Comment