A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.S→aS∣AA→aAb∣bAa∣ϵFor the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.
S→aS∣A
A→aAb∣bAa∣ϵ
For the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?

6 and 1

6 and 2

7 and 2

4 and 2

Similar Questions

Which of the following pairs have DIFFERENT expressive power?

Deterministic finite automata(DFA) and Non-deterministic finite automata(NFA)

Deterministic push down automata(DPDA)and Non-deterministic push down automata(NPDA)

Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine

Single-tape Turing machine and multi-tape Turing machine

Assume Statement S1 and S2 defined as:S1:L2-L1 is recursive enumerable Where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turnig machine is countable. Which of the following is true?

S1 is correct ans S2 is not correct

Both S1 and S2 are correct

Both S1 and S2 are not correct

S1 is not correct and S2 is correct

A context free language is called ambigous if ______________

it has 2 or more left derivations for some terminal string w e L(G)

it has 2 more or more right derivations for some terminal string w e L(G)

it has two or more left & right derivations for some terminal string w e L(G)

None of the mentioned

Which of the following statement is false ?

The CFG can be converted to Chomsky normal form

The CFG can be converted to Greibach normal form

CFG is accepted by pushdown automata

None of the mentioned

The context free grammer S->SS | oS1 | 1So | e generates

Equal number of O's and 1's

Unequal number of O's and 1's

Number of O's followd by any number of 1's

None of the mentioned

Which of the following statement is false ?

In derivation tree, the label of each leaf node is terminal

In derivation tree, the label of all nodes except leaf nodes is a variables

In derivation tree, if the root of a sub tree is X then it is called --tree

None of the mentioned

Push down automata excepts which language ?

Context Sensitive Language

Context free Language

Recursive Language

None of the mentioned

A regular Grammer is a ___________

CFG

Non CFG

English Grammer

None of the mentioned

A CFG is close under ________

Union

Kleene star

Concatenation

None of the mentioned

10.

Which of these does not belong to CFG ?

Terminal Symbol

Non Terminal Symbol

Start Symbol

End Symbol

THEORY OF AUTOMATA TOPICS