design a context sensitive grammar for string of a's whose length is a power of 2 ( 2^i) form ? i>=1

400 views Asked by At

Please explain how to design the context sensitive grammar of the above language. I am new to context sensitive grammar.

2

There are 2 answers

0
Olivia Pearls On

Can this be a solution?

 A -> aa 
 AA -> AAAA
 AAAA -> AAAAAAAA

and  so on
We get

A^i -> A^i.A^i , i>=1
and
A -> aa
0
Abdul Ghani On

The idea is to have a symbol that will 'track' across the sentiential form and double everything

S -> ERAE
RA -> AAR
RE -> LE | F
AL -> LA
EL -> ER
AF -> Fa
EF -> ε

This is just off the top of my head and may be wrong, but hopefully the idea comes through and you can give a proper answer.

I think the solution you gave is wrong as it seems to proprose an infinite number of rules - why not just have a rule for each possible string?