edited by
9,210 views
8 votes
8 votes

What is the number of steps required to derive the string $((()\; ())\; ())$ for the following grammar?

  • $S \to SS$
  • $S \to (S)$
  • $S \to \varepsilon$

 

  1. $10$       
  2. $12$            
  3. $15$            
  4. $16$
edited by

4 Answers

Best answer
12 votes
12 votes
ans -10

s -> (s)

   -->(ss)

  -->(s(s))

-->(s())

-->((s)())

-->((ss)())

-->(((s)s)())

-->((()s)())

-->((()(s))())

-->((()())())
selected by
1 votes
1 votes

If given grammar is as -   

S - > SS / (S) / e

then .. to derive the string   ( ( () () ) () ).. following steps to be followed -

1.S - > (S)

2.S - > (SS)                // S ->SS

3.S - > ( (S) S )           // S - > (S)

4.S - > ( (SS) S )         // S -> SS

5.S ->  ( ( S S) (S) )  // S - > (s) 

6.S ->  ( ( S (S)) (S) )  // S - > (s) 

7.S ->  ( ( (S) (S)) (S) )  // S - > (s) 

8.S ->  ( ( (S) (S)) () )  // S - > e

9.S ->  ( ( (S) ()) () )  // S - >  e

10.S ->  ( ( () ()) () )  // S - >  e  

Ans- 10 steps

edited by
1 votes
1 votes

$S$ $\rightarrow$ $(S)$
$\rightarrow$ $(SS)$
$\rightarrow$ $((S)S)$
$\rightarrow$ $((SS)S)$
$\rightarrow$ $(((S)S)S)$
$\rightarrow$ $((()S)S)$
$\rightarrow$ $((()(S))S)$
$\rightarrow$ $((()())S)$
$\rightarrow$ $((()())(S))$
$\rightarrow$ $((()())())$

No. of steps is equal to 10. So, right option is A.

Answer:

Related questions

3 votes
3 votes
1 answer
2
go_editor asked Jul 1, 2016
3,656 views
A computing architecture, which allows the user to use computers from multiple administrative domains to reach a common goal is called asGrid ComputingNeutral NetworksPar...
8 votes
8 votes
3 answers
3
go_editor asked Jul 1, 2016
4,762 views
Consider the following Deterministic Finite Automaton $M$.Let $S$ denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of str...
8 votes
8 votes
3 answers
4
go_editor asked Jul 1, 2016
4,648 views
Which of the following is not an optimization criterion in the design of a CPU scheduling algorithm?Minimum CPU utilizationMaximum throughputMinimum turnaround timeMinimu...