Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I don't know any general trick, but usually it helps to think about the language generated from each non-terminal.</p> <p>In your example language generated from B is obviously <code>L(B) = {b}^+</code>. Then you think about S rules, using the first rule, you can generate sentencial forms <code>{a^n.S.a^n | n &gt;= 1}</code>. If you use second rule on these sentencial forms or on S alone you can generate sentencial forms <code>{a^n.B.a^n | n &gt;= 1}</code>.</p> <p>Rest is pretty easy, you combine these two things and get <code>L(G) = {a^n.b^+.a^n | n &gt;= 1}</code></p> <p>By the way, in the definition of grammar terminals and nonterminals are sets, not tuples. And third component is production rules, not start symbol. So you should write <code>G = {{S, B}, {a, b}, P, S}</code>.</p> <p><strong>Edit</strong></p> <p>Actually, there is a way to solve your second example without much thinking just by following something like a cookbook. Because, language generated by your second context-free grammar is in fact regular.</p> <p>When you substitute rules for A, B and C to first three rules, you get</p> <pre><code>P' = {S -&gt; 0 | 3 | 6 | 9 | 0S | 3S | 6S | 9S | 1R | 4R | 7R | 2T | 5T | 8T R -&gt; 0R | 3R | 6R | 9R | 1T | 4T | 7T | 2 | 5 | 8 | 2S | 5S | 8S T -&gt; 0T | 3T | 6T | 9T | 1 | 4 | 7 | 1S | 4S | 7S | 2R | 5R | 8R} </code></pre> <p>And <code>P'</code> is regular grammar. Because of that, you can convert it to nondeterministic finite automaton (there is really simple way, look for it) and then convert resulting NFA to the regular expression (this is not so simple but if you follow an algorithm and don't get lost, you should be ok). And it from regular expression it is easy to tell what language it describes.</p> <p>Also, once you have NFA for this language you can look at it and determine what it does logically (it has something to do with counts of <code>1,4,7</code> and <code>2,5,8</code> in the word and <code>mod 3</code> of their difference. Think it through, it is your homework, afterall :-) )</p> <p>Of course, if you don't context-free grammar generating regular language you can't use this trick. There is no general way to tell what language the grammar generates (language equality problem for CFG's is undecideable), you have to think about every single example and look for similarities and patterns in it's logical structure. </p>
    singulars
    1. This table or related slice is empty.
    1. POFind out the language generated, given a context-free grammar?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USMartin Jonáš
    1. USMartin Jonáš
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFind out the language generated, given a context-free grammar?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COGood tip. Helps a lot, but how about more complicated examples? (see my edits). Thanks.
      singulars
      1. PO
      1. USgremo
    2. COGreat explanation. I've just found the way to represent the grammar as a NFA, it's quite simple as you said. However I'm still looking for a good starting point to learn the 2nd pass (regex). Can you point me in the right direction? Btw Answer accepted!
      singulars
      1. PO
      1. USgremo
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload