Question

Construct context-free grammars that generate the given set of strings. If the grammar has more than one variable, we will ask to write a sentence describing what sets of strings expect each variable in the grammar to generate. For example, if the grammar was:

I could say "C generates binary strings of length one, E generates (non-empty) even length binary strings, and O generates odd length binary strings." It is also fine to use a regular expression, rather than English, to describe the strings generated by a variable (assuming such a regular expression exists).

(1) RNA strings that can can fold into a lollipop shape.

The prefix CAGUAC and suffix GUACUG can together form the handle of the lollipop because they line up in such a manner that As are across from Us (or vice versa) and Cs are across from Gs (or vice versa). The candy part of the lollipop consists of the string GAUACG, which has length 6.

In general, an RNA string can fold into a lollipop shape if it can be written as xyz, where x and z contain at least two characters, y contains at least four characters, and the characters of x match up with those of z R, in the sense that the corresponding pairs of letters fall in the set {(A, U),(U, A),(C, G),(G, C)}.

Each RNA string is a string over the alphabet !A, C, G, U}. The string CAGUACGAUACGGUACUG can fold into a lollipop shape like this: 사-+ U CG

Answer 1

Context free grammar would be as follows:

Ps → TTTT Pa

Production:  

$\\S \rightarrow AP_{1}U|UP_{1}A|GP_{1}C|CP_{1}G\\$

This production produces first and last elements in string.

$\\ P_{1} \rightarrow AP_{2}U|UP_{2}A|GP_{2}C|CP_{2}G\\$

This production produces second element from start and end elements of string.

Since x and z part of string must of two pairs at least, S and P1 conforms this condition.

$\\P_{2} \rightarrow AP_{2}U|UP_{2}A|GP_{2}C|CP_{2}G|P_{3}\\$

P2 production may increase the handle part of the lollipop producing pairs or it may go to P3.

$\\P_{3} \rightarrow TTTTP_{4}\\$

P3 produces y part of the lollipop or curved part. It will atleast produce 4 RNA (not in pairs) symbols.

$\\P_{4} \rightarrow TP_{4}|\epsilon\\$

P4 production might increase the curved part or it may lead to termination.

$\\T \rightarrow A|C|G|U\\$

T produces the terminal symbols.

The parse for the given string "CAGUACGAUACGGUACUG" using above grammar is:

0 C. GE