Regular Languages & D-PDA - Free MCQ Practice Test with solutions, GATE

All regular languages can be accepted by a non deterministic finite automata and all context free languages can be accepted by a non deterministic push down automata.

he chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted

All the regular languages are the subset to context free languages and thus can be accepted using push down automata

e is the identity for concatenation. Thus, eR=R.

The string acbacba is unacceptable by the regular expression (a)*(a+cba).

Other mentioned options do not many of the combinations while option c seems most reliable.

All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.

 Here, the first mentioned b is fixed while the other can be zero or can be repeated any number of time.

Ant formal grammar is represented using a 4-tuple definition where V= finite set of variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain conditions based on the type of formal grammar.