StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy the need for terminals? Is my solution sufficient enough?
text
Body
copied!<p>I'm trying to get my head around context free grammars and I think I'm close. What is baffling me is this one question (I'm doing practise questions as I have an exam in a month's time):</p> <p><img src="https://i.stack.imgur.com/sIl7A.png" alt="enter image description here"></p> <p>I've come up with this language but I believe it's wrong. </p> <pre><code>S --> aSb | A | B A --> aA | Σ B --> bB | Σ </code></pre> <p>Apparently this is the correct solution:</p> <pre><code>S --> aSb | aA | bB A --> aA | Σ B --> bB | Σ </code></pre> <p>What I don't quite understand is why we have <code>S --> aSb | aA | bB</code> and not just <code>S --> aSb | A | B</code>. What is the need for the terminals? Can't I just call A instead and grab my terminals that way?</p> <p><strong>Testing to see if I can generate the string: aaabbbb</strong></p> <pre><code>S --> aSb --> aaSbb --> aaaSbbb --> aaaBbbb --> aaabbbb </code></pre> <p>I believe I generate the string correctly, but I'm not quite sure. I'm telling myself that the reason for <code>S --> aSb | aA | bB</code> is that if we start with <code>aA</code> and then replace <code>A</code> with <code>a</code>, we have two <code>a</code>'s which gives us our correct string as they're not equal, this can be done with b as well. Any advice is greatly appreciated.</p> <p><strong>Into the Tuple (G-4-tuple)</strong></p> <p><strong>V</strong> (None terminals) = {A, B} <br /> <strong>Σ</strong> (Terminals) = {a, b} <br /> <strong>P</strong> = { } // not quite sure how to express my solution in R? Would I have to use a test string to do so? <br /> <strong>S</strong> = A</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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