Newest questions tagged formal-grammars - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-10-17T03:31:26Z https://cs.stackexchange.com/feeds/tag?tagnames=formal-grammars&sort=newest https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/115817 0 Pushdown Automata - constructing a PDA to recognise a language with at least as many as as bs DoubleRainbowZ https://cs.stackexchange.com/users/110630 2019-10-14T03:15:52Z 2019-10-14T13:36:30Z <p>I am trying to construct a <strong>3-state</strong> PDA to recognise (I need to create a transition diagram for this question)</p> <pre><code>W = {w ∈ {a, b}^* | w contains at least as many as as bs} </code></pre> <p>My thought process so far has been this:</p> <pre><code> 1. Start off in q0 (q0 being an accept state) 2. add a $to the start of the stack (so you can see when the stack is empty), then transition to q1 (not an accept state). 3. If you receive an a: - if there is an a at the top of the stack, push the a on. - if there is a b at the top of the stack, pop the b. - if there is nothing on the top of the stack, push the a on. 4. If you receive a b: - if there is an a at the top of the stack, pop the a. - if there is a b at the top of the stack, push the b on. - if there is nothing on the top of the stack push the b on. 5. Once there is no more input: - if there is a$ at the top of the stack, transition to q3 (q3 being an accept state) - this means there was an equal number of as and bs - if there is an a at the top of the stack, transition to q3 (q3 being an accept state) - this means there was more as than bs if there is a b at the top of the stack, it means there was more bs than as, and thus we stay in q2, which is not an accept state. </code></pre> <p>(Sorry if this is hard to understand, I am not sure how to link those transition diagrams of the PDA's I've seen in some posts, if someone can tell me how to create one and link it in the post, I can update the post to be more understandable if needed)</p> <p>I have a few questions:</p> <ol> <li>Is this approach correct?</li> <li>Is the it correct to assume the machine is smart enough to know that if there isn't a b at the top of the stack, and I receive an a, it will push that a onto the stack (something like (q1, a, ε) -> (q1, a) to cover both cases where there is an a on the top of the stack and also the case where the stack has nothing in it))</li> <li>Do I need to push a \$at the start from q0 to q1 in the transition diagram (I've seen this to be the case for all PDAs on my lecture slide - which makes me think is it necessary to include if all machines need to do this - why is it not just implied?)</li> <li>I am ok to have 2 different scenarios to go to q2 right? Or would I be better doing something in q1, where if I have reached the end of my input queue, keep popping off as on the top of the stack until I reach the \$, then transition to q2? </li> </ol> <p>Sorry if anything is unclear - I am not super familiar with PDAs and the way to describe things - please let me know if I need to clarify anything.</p> https://cs.stackexchange.com/q/115751 1 Context-free grammar how to have unequal number of a's on either side of b DoubleRainbowZ https://cs.stackexchange.com/users/110630 2019-10-12T12:07:53Z 2019-10-13T03:29:59Z <p>I have been trying to create a CFG for the set <span class="math-container">$\{w=a^iba^j \mid i \neq j\}$</span>.</p> <p>To my understanding, there are essentially 2 scenarios, one where there are more <span class="math-container">$a$</span>s on the left side of <span class="math-container">$b$</span>, and one where there are more <span class="math-container">$a$</span>s on the right side of <span class="math-container">$b$</span>. So far I have come up with: <span class="math-container">\begin{align} S &amp;= TbR \mid RbT \\ T &amp;= aT \mid \varepsilon \\ R &amp;= TaT \end{align}</span> My intention is the have <span class="math-container">$R$</span> to always have more <span class="math-container">$a$</span>s than <span class="math-container">$T$</span>, however I don't think this is correct as <span class="math-container">$T$</span> can be greater than <span class="math-container">$R$</span> in this definition, as <span class="math-container">$R$</span> could take be just <span class="math-container">$a$</span> while <span class="math-container">$T$</span> is <span class="math-container">$aa$</span>.</p> <p>I need a bit of help defining 2 variables <span class="math-container">$T$</span> and <span class="math-container">$R$</span>, where <span class="math-container">$R$</span> always has more <span class="math-container">$a$</span>s than <span class="math-container">$T$</span>.</p> https://cs.stackexchange.com/q/115734 3 How to split a context-free language into three sub-languages? James https://cs.stackexchange.com/users/110623 2019-10-12T03:31:21Z 2019-10-12T12:15:10Z <p>I try to split the language <span class="math-container">$$L = \{a^ib^j \mid i \neq 2j, i \neq 3j\}$$</span> into three languages <span class="math-container">\begin{align} L_1 &amp;= \{a^ib^j \mid i &lt; 2j\} \\ L_2 &amp;= \{a^ib^j \mid 2j &lt; i &lt; 3j\} \\ L_3 &amp;= \{a^ib^j \mid i &gt; 3j\} \end{align}</span> and then use one more production <span class="math-container">$S = S_1|S_2|S_3$</span>, but I have no idea how to find the CFG for <span class="math-container">$L_2$</span>.</p> https://cs.stackexchange.com/q/115609 1 I want to design a context free grammar for the following [closed] Abhimanyu Bansal https://cs.stackexchange.com/users/110488 2019-10-08T16:37:10Z 2019-10-09T13:14:31Z <p>This below language</p> <p><span class="math-container">$$L = \{ w \in \{a, b\}^n : \lvert w\rvert \text{ mod } 3 = 0 \}$$</span> where <span class="math-container">$n \geq0$</span>.</p> https://cs.stackexchange.com/q/115590 2 LL(k) language and not LL(k) grammar J j https://cs.stackexchange.com/users/110473 2019-10-08T10:53:46Z 2019-10-09T15:41:28Z <p>I have nonambiguous and not LL(k) grammar which defines some language. How can I prove that I can't build some LL(k) grammar for this language?</p> <p>Grammar:</p> <p>S -> a b X c d | a X f</p> <p>X -> b X c | ε </p> https://cs.stackexchange.com/q/115578 0 Formal definition for strong equivalence of grammars/parse trees siracusa https://cs.stackexchange.com/users/108661 2019-10-08T02:07:47Z 2019-10-08T02:07:47Z <p>The <a href="https://en.wikipedia.org/wiki/Equivalence_(formal_languages)" rel="nofollow noreferrer">Wikipedia article</a> on equivalence of formal grammars defines weak and strong equivalence as follows:</p> <blockquote> <p>In formal language theory, <strong>weak equivalence</strong> of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same. In compiler theory the notion is distinguished from <strong>strong</strong> (or <strong>structural</strong>) <strong>equivalence</strong>, which additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both.</p> </blockquote> <p>The article states that there are different definitions for strong equivalance but doesn't give a formal description for any of them.</p> <p>Can anyone give an overview of the various definitions or at least give a formal description of the most common one, such that is can be used for an algorithm to check two parse trees for strong equivalance?</p> https://cs.stackexchange.com/q/115495 0 Are you allowed to use index variables in grammars? guskenny83 https://cs.stackexchange.com/users/17142 2019-10-06T10:27:50Z 2019-10-06T14:13:14Z <p>If we say that the grammar for the language <span class="math-container">$L = \{ww \mid w \in \{a,b\}^*\}$</span>, is:</p> <p><span class="math-container">\begin{align} S &amp;\rightarrow A_1A_2S \mid B_1B_2S \mid Z_2\\ A_2A_1 &amp;\rightarrow A_1A_2\\ A_2B_1 &amp;\rightarrow B_1A_2\\ B_2A_1 &amp;\rightarrow A_1B_2\\ B_2B_1 &amp;\rightarrow B_1B_2\\ A_2Z_2 &amp;\rightarrow Z_2a\\ B_2Z_2 &amp;\rightarrow Z_2b\\ Z_2 &amp;\rightarrow Z_1\\ A_1Z_1 &amp;\rightarrow Z_1a\\ B_1Z_1 &amp;\rightarrow Z_1b\\ Z_1 &amp;\rightarrow \lambda\\ \end{align}</span></p> <p>Here, the characters for each word are generated in the order they appear in a word <span class="math-container">$x \in L$</span> in pairs <span class="math-container">$A_1A_2$</span> and <span class="math-container">$B_1B_2$</span>, sorted using rules like <span class="math-container">$A_2B_1 \rightarrow B_1A_2$</span> and then converted with the end character, <span class="math-container">$Z_2$</span>.</p> <p>It can be seen that we could easily adapt this grammar to recognise the language <span class="math-container">$L = \{www \mid w \in \{a,b\}^*\}$</span>, by changing the start rule to <span class="math-container">$S \rightarrow A_1A_2A_3S \mid B_1B_2B_3S \mid Z_3$</span> and then adding more sorting and converting rules accordingly.</p> <p>I am struggling to see how we can generalise this to the language <span class="math-container">$L = \{w^i \mid w \in \{a,b\}^*,i \ge 2\}$</span>, however.</p> <p>Can you use a rule that looks like <span class="math-container">$S \rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i$</span>, where <span class="math-container">$i \ge 2$</span>?</p> <p>If so, can we use sorting rules that look like:</p> <p><span class="math-container">$A_kB_j \rightarrow B_jA_k$</span>, where <span class="math-container">$1 \le j &lt; k \le i$</span>,</p> <p>are you allowed to use variables in grammars like that? If so, you could just write the whole grammar as:</p> <p><span class="math-container">\begin{align} S &amp;\rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i,\text{ where } i \ge 2.\\ A_kA_j &amp;\rightarrow A_jA_k;\\ A_kB_j &amp;\rightarrow B_jA_k;\\ B_kA_j &amp;\rightarrow A_jB_k;\\ B_kB_j &amp;\rightarrow B_jB_k,\text{ where } 1 \le j &lt; k \le i.\\ A_kZ_k &amp;\rightarrow Z_ka;\\ B_kZ_k &amp;\rightarrow Z_kb;\\ Z_k &amp;\rightarrow Z_{k-1},\text{ where } 1 \le k \le i.\\ Z_0 &amp;\rightarrow \lambda\\ \end{align}</span></p> <p>I have never seen a grammar with variables like this though. But I guess they aren't really variables, because <span class="math-container">$i$</span> needs to be specified before the computation begins. So, what you would actually be doing is choosing some <span class="math-container">$i$</span> and then instantiating a version of that grammar, specifially for a given <span class="math-container">$i$</span>. Once the computation has begun, there are no actual variables in the grammar and, effectively, we are just providing rules to build a grammar for the language, based on some <span class="math-container">$i$</span>.</p> <p>I can think of an algorithm for a Turing machine that could recognise that language (by partitioning the input string <span class="math-container">$w$</span> in all possible ways such that <span class="math-container">$|w|\text{ mod }n = 0$</span>, where <span class="math-container">$n$</span> is the number of substrings, and then checking each partition to see if any of them have exactly the same substrings), so the language must be recursively enumerable - I just can't think how to write something like this as a grammar without making rules with variables (if you arent allowed to.. if you are allowed to then I think what I have is okay..)</p> <p><strong>EDIT:</strong> </p> <p>I think I might have come up with a way of solving the problem without using index variables:</p> <p><span class="math-container">\begin{align} S &amp;\rightarrow LZ_1XR\\ X &amp;\rightarrow A_0X \mid B_0X \mid \lambda\\ Z_1A_0 &amp;\rightarrow A_1A_0Z_1\\ Z_1B_0 &amp;\rightarrow B_1B_0Z_1\\ A_0A_1 &amp;\rightarrow A_1A_0\\ A_0B_1 &amp;\rightarrow B_1A_0\\ B_0A_1 &amp;\rightarrow A_1B_0\\ B_0B_1 &amp;\rightarrow B_1B_0\\ LA_1 &amp;\rightarrow A_1L\\ LB_1 &amp;\rightarrow B_1L\\ Z_1R &amp;\rightarrow RZ_0 \mid Y_0\\ A_0Z_0 &amp;\rightarrow Z_0A_0\\ B_0Z_0 &amp;\rightarrow Z_0B_0\\ LZ_0 &amp;\rightarrow LZ_1\\ A_0Y_0 &amp;\rightarrow Y_0a\\ B_0Y_0 &amp;\rightarrow Y_0b\\ LY_0 &amp;\rightarrow Y_1\\ A_1Y_1 &amp;\rightarrow Y_1a\\ B_1Y_1 &amp;\rightarrow Y_1b\\ Y_1 &amp;\rightarrow \lambda\\ \end{align}</span></p> <p>Here, an initial string <span class="math-container">$w$</span> is generated between <span class="math-container">$L$</span> and <span class="math-container">$R$</span> markers using <span class="math-container">$A_0$</span> and <span class="math-container">$B_0$</span> non-terminals, then the <span class="math-container">$Z_1$</span> character is moved to the right of the string, making a copy of the word in <span class="math-container">$A_1$</span> and <span class="math-container">$B_1$</span> non-terminals which are then shuffled to the left of the <span class="math-container">$L$</span> marker, and this process is repeated until you have <span class="math-container">$i$</span> copies of the string <span class="math-container">$w$</span>, at which point the <span class="math-container">$Z_1$</span> changes and runs across the string to the left changing all the non-terminals into terminals.</p> <p>I think this should work fine.. but it is a pretty complicated grammar, so my initial question still remains, are you allowed to use index variables to make rules to generate grammars like I did in the original question?</p> https://cs.stackexchange.com/q/115471 1 Ambiguos Grammar detection algorithm edoardottt https://cs.stackexchange.com/users/110353 2019-10-05T12:02:21Z 2019-10-05T22:47:46Z <p>I tried to solve if a grammar is ambiguous or not. I know that I have to find a word that can be generate by two different leftmost derivations. Is there any algorithm to find a word that, if the grammar is ambiguous, can be generated by two different trees? <a href="https://cs.stackexchange.com/questions/41586/ambiguous-context-free">This question</a> is different.</p> https://cs.stackexchange.com/q/115355 2 What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$? Ignat Insarov https://cs.stackexchange.com/users/84119 2019-10-02T13:29:06Z 2019-10-02T18:54:51Z <p>In other words, what is the likelihood that a recognizer of a given regular language will accept a random string of length <span class="math-container">$n$</span>?</p> <p>&nbsp;</p> <p><strong>If there is only a single non-terminal <span class="math-container">$A$</span></strong>, then there are only two kinds of rules:</p> <ol> <li>Intermediate rules of the form <span class="math-container">$S \to \sigma S$</span>.</li> <li>Terminating rules of the form <span class="math-container">$S \to \sigma$</span>.</li> </ol> <p>Such a grammar can then be rewritten in shorthand with exactly two rules, thusly:</p> <p><span class="math-container">\left\{\begin{align} &amp;S \enspace \to \enspace \{\sigma, \tau, \dots\} S = ΤS\\ &amp;S \enspace \to \enspace \{\sigma, \tau, \dots\} = Τ'\\ \end{align}\right.\\ \space \\ (Τ, Τ' \subset \Sigma)</span></p> <p>So, we simply choose one of the <span class="math-container">$Τ$</span> <em>(this is Tau)</em> symbols at every position, except for the last one, which we choose from <span class="math-container">$Τ'$</span>.</p> <p><span class="math-container">$$d = \frac {\lvert Τ\rvert^{n - 1} \lvert Τ' \rvert} {\lvert\Sigma\rvert^n}$$</span></p> <p>I will call an instance of such language <span class="math-container">$L_1$</span>.</p> <p>&nbsp;</p> <p><strong>If there are two non-terminals</strong>, the palette widens:</p> <ol> <li>Looping rules of the form <span class="math-container">$S \to \sigma S$</span>.</li> <li>Alternating rules of the form <span class="math-container">$S \to \sigma A$</span>.</li> <li>Terminating rules of the form <span class="math-container">$S \to \sigma$</span>.</li> <li>Looping rules of the form <span class="math-container">$A \to \sigma A$</span>.</li> <li>Alternating rules of the form <span class="math-container">$A \to \sigma S$</span>.</li> <li>Terminating rules of the form <span class="math-container">$A \to \sigma$</span>.</li> </ol> <p>In shorthand: <span class="math-container">\left\{\begin{align} &amp;S \enspace \to \enspace Τ_{SS} S \\ &amp;S \enspace \to \enspace Τ_{SA} A \\ &amp;S \enspace \to \enspace Τ_{S\epsilon} \\ &amp;A \enspace \to \enspace Τ_{AA} A \\ &amp;A \enspace \to \enspace Τ_{AS} S \\ &amp;A \enspace \to \enspace Τ_{S\epsilon} \\ \end{align}\right.\\ \space \\ (Τ_{SS}, Τ_{SA}, Τ_{S\epsilon}, Τ_{AA}, Τ_{AS}, Τ_{S\epsilon} \subset \Sigma)</span></p> <p>Happily, we may deconstruct this complicated language into words of the simpler languages <span class="math-container">$L_1$</span> by taking only a looping rule and either an alternating or a terminating shorthand rule. This gives us four languages that I will intuitively denote <span class="math-container">$L_{1S}, L_{1S\epsilon}, L_{1A}, L_{1A\epsilon}$</span>. I will also say <span class="math-container">$L^n$</span> meaning all the sentences of <span class="math-container">$L$</span> that are <span class="math-container">$n$</span> symbols long.</p> <p>So, the sentences of this present language <em>(let us call it <span class="math-container">$L_2$</span>)</em> consist of <span class="math-container">$k$</span> alternating words of <span class="math-container">$L_{1S}$</span> and <span class="math-container">$L_{1A}$</span> of lengths <span class="math-container">$m_1 \dots m_k, \sum_{i = 1 \dots k}m_i = n$</span>, starting with <span class="math-container">$L_{1S}^{m_1}$</span> and ending on either <span class="math-container">$L_{1S\epsilon}^{m_k}$</span> if <span class="math-container">$k$</span> is odd or otherwise on <span class="math-container">$L_{1A\epsilon}^{m_k}$</span>.</p> <p>To compute the number of such sentences, we may start with the set <span class="math-container">$\{P\}$</span> of integer partitions of <span class="math-container">$n$</span>, then from each partition <span class="math-container">$P = \langle m_1\dots m_k \rangle$</span> compute the following numbers:</p> <ol> <li><p>The number <span class="math-container">$p$</span> of distinct permutations <span class="math-container">$\left(^k_Q\right)$</span> of the constituent words, where <span class="math-container">$Q = \langle q_1\dots\ \rangle$</span> is the number of times each integer is seen in <span class="math-container">$P$</span>. For instance, for <span class="math-container">$n = 5$</span> and <span class="math-container">$P = \langle 2, 2, 1 \rangle$</span>, <span class="math-container">$Q = \langle 1, 2 \rangle$</span> and <span class="math-container">$p = \frac{3!}{2! \times 1!} = 3$</span></p></li> <li><p>The product <span class="math-container">$r$</span> of the number of words of lengths <span class="math-container">$m_i \in P$</span>, given that the first word comes from <span class="math-container">$L_{1S}$</span>, the second from <span class="math-container">$L_{1A}$</span>, and so on <em>(and accounting for the last word being of a slightly different form)</em>:</p> <p><span class="math-container">$$r = \prod_{i = 1, 3\dots k - 1}\lvert L_{1S}^{m_i} \rvert \times \prod_{i = 2, 4\dots k - 1}\lvert L_{1A}^{m_i} \rvert \times \begin{cases} &amp; \lvert L_{1S\epsilon}^{m_k} \rvert &amp;\text{if m is odd}\\ &amp; \lvert L_{1A\epsilon}^{m_k} \rvert &amp;\text{if m is even}\\ \end{cases}$$</span></p></li> </ol> <p>If my thinking is right, the sum of <span class="math-container">$p \times r$</span> over the partitions of <span class="math-container">$n$</span> is the number of sentences of <span class="math-container">$L_2$</span> of length <span class="math-container">$n$</span>, but this is a bit difficult for me.</p> <p>&nbsp;</p> <p><strong>My questions:</strong></p> <ul> <li>Is this the right way of thinking? </li> <li>Can it be carried onwards to regular grammars of any complexity?</li> <li>Is there a simpler way?</li> <li>Is there prior art on this topic?</li> </ul> https://cs.stackexchange.com/q/115285 4 Acyclic Manhattan turtle Ignat Insarov https://cs.stackexchange.com/users/84119 2019-09-30T17:59:26Z 2019-10-01T08:50:12Z <p>There is a grammar that describes the walks of a turtle around Manhattan, such that the turtle always returns home. It is described in the book <a href="https://dickgrune.com/Books/PTAPG_2nd_Edition/" rel="nofollow noreferrer"><em>"Parsing Techniques"</em> by Dick Grune and Ceriel J.H. Jacobs</a>, page 18. Unfortunately, I could not find a source online, but the rules are rather simple:</p> <p><span class="math-container">G = \left\langle \{0\}, \Sigma = \{N, S, E, W\}, R, 0 \right\rangle \\[2ex] R = \left\{ \begin{align} &amp; 0 \to N 0 S \\ &amp; 0 \to E 0 W \\ &amp; 0 \to \epsilon \\[2ex] &amp; N S \to S N \\ &amp; \dots \quad \scriptsize{(\text{11 other pairs of distinct } \sigma, \tau \in \Sigma)} \end{align} \right.</span></p> <p>I actually went ahead and generated some sentences of this grammar. Example:</p> <p><span class="math-container">$$NENNEENSWWSWSS$$</span></p> <p><em>(Sentence № 10617)</em></p> <p>A sentence such as this one corresponds to a graph, like the following:</p> <pre><code>+-----------------+ | | | | | * | | ⭣ | | * ⭠ * ⭠ * | | ⭣ | | * ⭠ * | | ⭣ ⭡ | | * ⭢ * | | ⭣ | | + | | | | | +-----------------+ </code></pre> <p><em>(Or, rather, to a path on the square lattice of Manhattan, but a path defines a subgraph.)</em></p> <p>As this example shows, the walk of our turtle will sometimes have loops.</p> <p>&nbsp;</p> <p><strong>How hard would it be to compose a grammar that generates exactly the acyclic walks?</strong></p> <p><strong>P.S.</strong> As pointed out in comments, there will always be at least one cycle. Let us call that cycle <em>"trivial"</em> and say <em>"a grammar that generates exactly the walks with only the trivial cycle"</em> instead.</p> https://cs.stackexchange.com/q/115188 0 Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion siracusa https://cs.stackexchange.com/users/108661 2019-09-28T09:20:35Z 2019-09-28T09:20:35Z <p>It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-recursive rules to equivalent grammars that don't have such rules.</p> <p>For example, a simple left-recursive grammar</p> <p><span class="math-container">\begin{alignat}{2} &amp;E &amp;&amp;\to E \ \text{'-'}\ V \ \vert \ V\\ &amp;V &amp;&amp;\to \text{'a'} \ \vert\ \text{'b'} \end{alignat}</span> can be converted to an equivalent right-recursive one <span class="math-container">\begin{alignat}{2} &amp;E &amp;&amp;\to V \ E'\\ &amp;E' &amp;&amp;\to \text{'-'}\ V \ E' \ \vert \ \varepsilon\\ &amp;V &amp;&amp;\to \text{'a'} \ \vert\ \text{'b'} \end{alignat}</span> that accepts the same language.</p> <p>The problem with that conversion in that the parse trees for the same input string look fundamentally different. In the first case the result is a left-leaning tree, reflecting the left-associativity of the subtraction operator. On the other hand, the parse tree for the second grammar would yield a right-leaning tree, which makes it harder to process or evaluate the built parse tree.</p> <p>In terms of equivalence, this conversion yields a non-left-recursive grammar that is <em>weakly</em> equivalent to the original one, i.e. accepting the same language, but not <em>strongly</em> equivalent. The latter also requires structurally equivalent parse trees.</p> <p>For every left-recursive context-free grammar, does there exist a non-left-recursive, strongly equivalent version that describes the same language? If so, how would an algortihm look like that performs such a conversion?</p> https://cs.stackexchange.com/q/114996 0 Is Python's Grammar in a known Category between CFG and CSG? Erotemic https://cs.stackexchange.com/users/90183 2019-09-21T20:19:35Z 2019-09-21T20:19:35Z <p>I have a high level understanding of formal languages and grammars, and I'm familiar with the four major types of grammars in Chomsky hierarchy. I was interested in knowing the classification of Python's grammar. A quick search yielded some quick, but incomplete answers. </p> <p><a href="http://trevorjim.com/python-is-not-context-free/" rel="nofollow noreferrer">http://trevorjim.com/python-is-not-context-free/</a></p> <p><a href="https://www.reddit.com/r/compsci/comments/1f2e0w/ive_heard_of_contextfree_grammars_cfgs_but_are/" rel="nofollow noreferrer">https://www.reddit.com/r/compsci/comments/1f2e0w/ive_heard_of_contextfree_grammars_cfgs_but_are/</a></p> <p><a href="https://cs.stackexchange.com/questions/77989/is-python-a-context-free-language/89726#89726">Is Python a context-free language?</a></p> <p>The immediate takeaway from most resources it that Python's grammar is not a context free grammar (CFG). But that doesn't answer the question of what it is. Looking deeper I found that its a complete context sensitive grammar (CSG) either. But still no classification. </p> <p>At this point the conclusion was that there must exist classes of grammars between CFGs and CSGs, but I had never heard anything about these. </p> <p>What I do understand is Python's lexer (which transforms character sequences into tokens) does something that a CFG cannot do: it tracks the level of indentation and yields special INDENT DEDENT tokens. After this transformation resulting tokens are context-free and can be parsed into an abstract syntax tree. Thus the grammar on tokens is a CFG, but the grammar on characters uses slightly power power than a CFG can provide alone. I want to know if there is a classification for this type of grammar. What is between a CFG and a CSG?</p> <p>After a bit more searching I stumbled on this table at the bottom of a Wikpedia article: <a href="https://en.wikipedia.org/wiki/Linear_bounded_automaton#External_links" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Linear_bounded_automaton#External_links</a></p> <p>Here is an image of that table:</p> <p><a href="https://i.stack.imgur.com/RwMLG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/RwMLG.png" alt="enter image description here"></a></p> <p>Cool, I found that there are known grammars between CFG and CSGs. But I'm not an expert on formal languages, so I don't know how I would go about determining which if any of these categories Python's grammar belonged to. </p> <p>Is it a "Positive range concatenation", "Indexed", "Thread automation's Grammar", "Linear context-free rewriting system", "Tree-adjoining"? Is it none of these; if so does what it is have a classification? </p> <p>Note: The full grammar specification of Python 3 can be found here: <a href="https://docs.python.org/3/reference/grammar.html" rel="nofollow noreferrer">https://docs.python.org/3/reference/grammar.html</a></p> https://cs.stackexchange.com/q/114751 2 Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar) Edmundo Del Gusto https://cs.stackexchange.com/users/109561 2019-09-14T17:23:00Z 2019-09-15T15:35:16Z <p>I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer):</p> <p>Show that <span class="math-container">$L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$</span> is context-sensitve.</p> <p>I could easily construct a LBA for this language. But since the notation/construction of LBAs weren't really explained, I would have to define it in the exam.</p> <p>So I assume this task was expected to be done by constructing a context-sensitive grammar.</p> <p><strong>NOTE:</strong> In our lecture the definition of a context-sensitive grammar was in fact the definition of a noncontracting grammar. So any rule like this <strong>x -> y</strong> is allowed if <strong>|x| &lt;= |y|</strong></p> <p>So this is allowed:</p> <pre><code>aAb -&gt; bXaa </code></pre> <p>My best idea goes like this:</p> <pre><code>S -&gt; AB B -&gt; bB | b A -&gt; CA | C Cb -&gt; abC Ca -&gt; aC </code></pre> <p>so to generate <code>aaabaaabaaab</code> I do this:</p> <pre><code>S AB AbB AbbB Abbb CAbbb CCAbbb CCCbbb (let all C-Variables run through the word and leave an 'a' before every 'b') CCabCbb CCababCb CCabababC ... aaabaaabaaabCCC </code></pre> <p>But I can't make all the 'C'-Variables disappear.</p> https://cs.stackexchange.com/q/114709 1 Is following grammar has language which is inherently ambiguous? Vimal Patel https://cs.stackexchange.com/users/101527 2019-09-13T07:49:00Z 2019-09-13T08:42:17Z <p>Grammar is as follow:</p> <p><span class="math-container">$S \rightarrow aaAb | aab | A$</span></p> <p><span class="math-container">$A \rightarrow aaAb | aAb | \epsilon$</span></p> <p>I think that this grammar has equivalent unambiguous grammar as follow.</p> <p>Let’s first rewrite the grammar as below such that this grammar has same language as one in question:</p> <p><span class="math-container">$S \rightarrow aaSb | aSb | \epsilon$</span></p> <p>Because this grammar generates <span class="math-container">$L = \{a^nb^m: m \le n \le 2m\}$</span></p> <p>This grammer is just using two production in some order to derive string and then use null production to complete derivation.</p> <p>So, idea is that we can some how order use of production such that any use of <span class="math-container">$S \rightarrow aaSb$</span> production does not come before use of any production of form <span class="math-container">$S \rightarrow aSb$</span>. And following this idea it’s very easy to generate this grammar.</p> <p><span class="math-container">$S \rightarrow aSb | A$</span></p> <p><span class="math-container">$A \rightarrow aaAb | \epsilon$</span></p> <p>.</p> <p>Another arguments goes as follow:</p> <p>Because <span class="math-container">$2k_1 + k_2 = n$</span> and <span class="math-container">$k_1 + k_2 = m$</span> for some <span class="math-container">$nonnegetive \space integer \space k_1, k_2$</span>. (here <span class="math-container">$k_1$</span> and <span class="math-container">$k_2$</span> corresponds to number of use of production of form <span class="math-container">$S \rightarrow aSb$</span> and <span class="math-container">$S \rightarrow aaSb$</span> respectively.)</p> <p>After solving the above equations we find that <span class="math-container">$k_1 = m-n$</span> hence value of <span class="math-container">$k_1$</span> will be unique for any perticular string. Which means that we must have to use some fix number of times the production of form <span class="math-container">$S \rightarrow aSb$</span>. Which consequenly means that in our last rewritten grammer there is a fix point for a perticular string where you have to perform <span class="math-container">$S \rightarrow A$</span>.</p> <p>Please help me with this. I want to know whether this language is inherenly ambigous or not?</p> https://cs.stackexchange.com/q/114694 4 Language containing all unambiguous grammars giusti https://cs.stackexchange.com/users/62044 2019-09-12T19:41:19Z 2019-09-12T22:12:32Z <p>Suppose <span class="math-container">$L$</span> is the language of the <em>unambiguous grammars</em>. That is, a sentence <span class="math-container">$w\in{}L$</span> if it is a string that describes an unambiguous context-free grammar.</p> <p>Considering that deciding whether a context-free grammar is ambiguous is non-decidable, would it be correct to say that <span class="math-container">$L$</span> exists but is not recursively enumerable?</p> https://cs.stackexchange.com/q/114633 0 Whether following language is linear or not? Vimal Patel https://cs.stackexchange.com/users/101527 2019-09-11T10:36:30Z 2019-09-11T10:42:25Z <p>I have a language <span class="math-container">$L= \{a^nb^nc^m : n, m \ge 0\}$</span>.</p> <p>Now, I wanted to determine whether this language is linear or not.</p> <p>So, I came up with this grammar:</p> <p><span class="math-container">$S \rightarrow A\thinspace|\thinspace Sc$</span></p> <p><span class="math-container">$A \rightarrow aAb \thinspace | \thinspace \lambda$</span></p> <p>I'm pretty sure(not completely however) that this grammar is linear and consequently language too is linear. </p> <hr> <p>Now, when I use pumping lemma of linear languages with <span class="math-container">$w$</span>, <span class="math-container">$v$</span> and <span class="math-container">$u$</span> chosen as follow I find that this language is not linear.</p> <p><span class="math-container">$w = a^nb^nc^m, \space v = a^k, \space y=c^k$</span></p> <p><span class="math-container">$w_0 = a^{n-k}b^nc^{n-k}$</span></p> <p>now, <span class="math-container">$w_0 \notin L \space (\because n_a \neq n_b)$</span></p> <p>So, I'm unable to find whether the language is linear or not and what goes wrong in above logic with either case. Please help.</p> https://cs.stackexchange.com/q/113573 0 With a grammar, does precedence and associativity change the accepted language? fundagain https://cs.stackexchange.com/users/109347 2019-09-09T17:06:15Z 2019-09-09T20:42:06Z <p>When parsing, certainly precedence and associativity effect the AST. But, do precedence and associativity alter the set of accepted sentences? In other words, can precedence and associativity be "ignored" (defined in some random precedence all associating left, say) in the grammar, and then the AST fixed later based on (possibly dynamic) precedence and associativity conditions? </p> <p>I am concerned only with LL grammars and their common variants.</p> https://cs.stackexchange.com/q/113006 0 Create automata from non regular grammar cieco1109 https://cs.stackexchange.com/users/108805 2019-08-23T15:09:55Z 2019-09-03T08:55:48Z <p>I have two grammars: </p> <pre><code> L → ε | aLcLc L → ε | aLcLc | LL </code></pre> <p>This two grammars are equals but the first one is regular, so it produces a regular language and a Finite State Automata. Instead, the second one is non regular but it might produces a regular language.<br> To prove it, I want to create two differentes automata: the first one should be a correct automata and if the second one can't be create then the language is not regular. Are all this statments correct?<br> If so, can someone help me build these two automata? Thank you!</p> https://cs.stackexchange.com/q/112758 1 How do i tell if a grammar is regular or not? alexW https://cs.stackexchange.com/users/102263 2019-08-15T01:27:44Z 2019-08-15T15:01:14Z <p>I know that a regular grammar has a definition </p> <p><span class="math-container">\begin{align}S &amp;\to aS\\ S &amp;\to \lambda \end{align}</span></p> <p>But I dont really know how to apply this information to check whether or not a grammar is regular...</p> <p>So for example I have a grammar <span class="math-container">\begin{align}S &amp;\to aSbSb\\ S &amp;\to \lambda \end{align}</span></p> <p>If I compare it to the definition of a regular grammar this is not a regular grammar right? Which also means that I can't turn this into a regex.</p> <p>Also could you please give me an example of a regular grammar and a non-regular grammar hopefully that will solidify my understanding.</p> https://cs.stackexchange.com/q/112683 0 Why are CFL not closed under set difference, and complementation? [duplicate] Neel Mishra https://cs.stackexchange.com/users/108407 2019-08-12T06:36:48Z 2019-08-12T06:36:48Z <div class="question-status question-originals-of-duplicate"> <p>This question already has an answer here:</p> <ul> <li> <a href="/questions/19266/examples-of-context-free-languages-with-a-non-context-free-complements" dir="ltr">Examples of context-free languages with a non-context-free complements</a> <span class="question-originals-answer-count"> 2 answers </span> </li> </ul> </div> <p>I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.</p> https://cs.stackexchange.com/q/112481 3 Context-free grammar of the concatenation of a string S and subsequence of reversed S Ramen with Eggs https://cs.stackexchange.com/users/108124 2019-08-06T03:12:40Z 2019-08-06T15:59:44Z <p>I have to find a Context-Free grammar that generates the language:</p> <p><span class="math-container">$L_1 = \{x\#y\ |\ y$</span> is a subsequence of <span class="math-container">$x^R$</span>, and <span class="math-container">$x\in\{a,b\}^*\}$</span>, <span class="math-container">$\Sigma=\{a,b,\#\}$</span></p> <hr> <p>The concatenation of two mutually reversed strings are pretty simple, but I just can't figure out how to express "plugging in random terminals in <span class="math-container">$x$</span>" so that <span class="math-container">$x^R$</span> could contain <span class="math-container">$y$</span> as its subsequence.</p> https://cs.stackexchange.com/q/111793 1 Calculating LL(1) grammar Athl1n3 https://cs.stackexchange.com/users/77408 2019-07-13T17:19:10Z 2019-07-13T20:30:57Z <p>I am trying to calculate the First and Follow of the following grammar</p> <pre><code>S-&gt;ABC A-&gt;Aa A-&gt;aB B-&gt;Bb B-&gt; epsilon C-&gt; Cc C-&gt; Epsilon </code></pre> <p>I have calculated the firsts and it is all good</p> <pre><code>Follow(A) = {a,b,c,$} </code></pre> <p>What is confusing me is the follow of B, I get <code>Follow(B) = Follow(A)</code> But on the other hand, I have a solution for the grammar that states that the <code>follow(B) = {b,c,$}</code></p> <p>So which one is the right one?</p> https://cs.stackexchange.com/q/111541 0 grammar for the no.of a's one more than no. of b's [duplicate] gokul goku https://cs.stackexchange.com/users/106797 2019-07-06T06:33:32Z 2019-07-06T06:33:32Z <div class="question-status question-originals-of-duplicate"> <p>This question already has an answer here:</p> <ul> <li> <a href="/questions/56651/cfg-for-the-language-number-of-as-number-of-bs-2" dir="ltr">CFG for the language &ldquo;number of a&#39;s = number of b&#39;s + 2&rdquo;</a> <span class="question-originals-answer-count"> 1 answer </span> </li> </ul> </div> <p>write the grammar for the following</p> <p>L = {w : na (w)= nb (w) + 1}.</p> <p>*</p> <blockquote> <p>no. of a’s is one more than no. of b’s</p> </blockquote> <p>*</p> https://cs.stackexchange.com/q/111384 2 Why $P$ cannot have NULL string in Arden's Theorem? PS Nayak https://cs.stackexchange.com/users/78596 2019-07-01T16:50:29Z 2019-07-01T18:26:33Z <p>Arden's Theorem says that in the equation <span class="math-container">$R=Q+RP$</span>, the <span class="math-container">$P$</span> cannot have NULL string. In this respect,the theorem will not be valid for the expression <span class="math-container">$R=Q+R(NULL+01)$</span>. Am I correct? If so, then what will be the justification?</p> https://cs.stackexchange.com/q/111287 0 Is $LR(k) \subset SLR(k+1)$ for $k=1,2,...$? [duplicate] anir https://cs.stackexchange.com/users/49261 2019-06-29T12:01:53Z 2019-06-29T12:01:53Z <div class="question-status question-originals-of-duplicate"> <p>This question already has an answer here:</p> <ul> <li> <a href="/questions/43/language-theoretic-comparison-of-ll-and-lr-grammars" dir="ltr">Language theoretic comparison of LL and LR grammars</a> <span class="question-originals-answer-count"> 1 answer </span> </li> </ul> </div> <p>I know that:</p> <blockquote> <p><strong>Point 1</strong>: Set of languages accepted by <span class="math-container">$LR(0)$</span> parsers <span class="math-container">$\subset$</span> Set of languages accepted by <span class="math-container">$SLR(1)$</span> parsers </p> </blockquote> <p>Does this logic hold for higher <span class="math-container">$k$</span>'s? That is, does following fact hold?</p> <blockquote> <p><strong>Point 2</strong>: Set of languages accepted by <span class="math-container">$LR(k)$</span> parsers <span class="math-container">$\subset$</span> Set of languages accepted by <span class="math-container">$SLR(k+1)$</span> parsers, for <span class="math-container">$k=1,2,...$</span></p> </blockquote> <p>Also I have just <a href="https://stackoverflow.com/a/20208748">came across</a> the fact that every <span class="math-container">$LR(k)$</span> language is parseable by <span class="math-container">$LR(1)$</span> parser. So, I guess, point 2 seems trivial for <span class="math-container">$k&gt;2$</span> and all we need to prove is:</p> <blockquote> <p>Whether <span class="math-container">$LR(1)\subset SLR(2)$</span> ? </p> </blockquote> <p>Is it so?</p> <p><strong>PS:</strong> I have not read this paper and dont know if it is related, but linking it anyway: <a href="https://www.sciencedirect.com/science/article/pii/0020019091901528" rel="nofollow noreferrer">SLR(k) covering for LR(k) grammars</a></p> https://cs.stackexchange.com/q/111269 0 Does SLR(0), LALR(0) exists? anir https://cs.stackexchange.com/users/49261 2019-06-28T19:42:18Z 2019-06-28T19:42:18Z <p>I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these two links which talk about LL(0): <a href="https://stackoverflow.com/a/5253867/6357916">1</a> and <a href="https://www.quora.com/Compilers-Whats-the-difference-between-LL-0-and-LR-0-parsers-Is-there-such-a-thing-as-LL-0-parsers/answer/Christopher-F-Clark-1" rel="nofollow noreferrer">2</a>. These answers are quite satisfiable in explaining LL(0) grammars. However I still dont find anything on SLR(0) and LALR(0). Do they even exist? If yes, in what form?</p> https://cs.stackexchange.com/q/111233 0 Proving correctness of LR parser facts anir https://cs.stackexchange.com/users/49261 2019-06-27T19:48:13Z 2019-06-27T20:37:10Z <p>I have came across following facts while reading some compilers related text. However I did not find them in any standard reference book (mainly dragon book). Are they correct? If yes, how can we prove them?</p> <blockquote> <p><strong>Fact:</strong></p> <ol> <li>If there is a λ-free LL(1) grammar for a language, then we can also prepare SLR(1) grammar for it. (λ-free means: there is no null productions of the form <span class="math-container">$A\rightarrow\lambda$</span> for any non terminal <span class="math-container">$A$</span>)</li> <li>LL(1) grammar whose variable are all able to derive a not null string is LALR(1). (able to derive a not null string means: there may exist null production <span class="math-container">$A\rightarrow \lambda$</span>, but along with it, there should also exist non-null production <span class="math-container">$A\rightarrow \alpha$</span> for every such <span class="math-container">$A$</span>, where <span class="math-container">$\alpha = (V+t)^*$</span> where <span class="math-container">$V$</span> is any non terminal and <span class="math-container">$t$</span> is any terminal)</li> </ol> </blockquote> https://cs.stackexchange.com/q/111114 1 Confusion with first condition of Chomsky Normal Form Questionairre4367 https://cs.stackexchange.com/users/106873 2019-06-24T17:28:02Z 2019-06-24T22:56:07Z <p>I had a very quick question when it comes to CFG (more specifically the attributes of CNF). I've been browsing over some examples and I've come across a few that confuse me. One such example is this:</p> <p><span class="math-container">\begin{align}S&amp;\to XA|BB\\ B&amp;\to b|SB\\ X&amp;\to b\\ A&amp;\to a\\ \end{align}</span></p> <p>It is stated that this is indeed in CNF, but my confusion lies in the fact that under most rules it is stated that if the starting state <span class="math-container">$S$</span> exists in some RHS (in this case <span class="math-container">$B\to b|SB$</span>) we must create a rule that states <span class="math-container">$S'\to S$</span>.</p> <p>Since that doesn't exist in this example, why is this considered to be in CNF? I also understand the rules of CNF, I also see that this example technically satisfies all those rules, so I am wondering if that is the reason?</p> <p><strong><em>Rules:</em></strong> <span class="math-container">\begin{align}A&amp;\to a\\ A&amp;\to BC\\ \end{align}</span></p> <p>Thank you for the help in advance! </p> <p>Here is the link to the question for reference ( it deals with CFG TO GNF) <a href="https://www.geeksforgeeks.org/converting-context-free-grammar-greibach-normal-form/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/converting-context-free-grammar-greibach-normal-form/</a> </p> https://cs.stackexchange.com/q/111069 0 How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts? anir https://cs.stackexchange.com/users/49261 2019-06-23T06:13:58Z 2019-06-27T19:14:02Z <p>I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:</p> <blockquote> <p>When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing table may involve FIRST-FIRST and/or FIRST-FOLLOW conflicts, whereas LR parsing table may involve SR and/or RR conflicts. When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar. Does this means, eliminating LL conflicts also somehow eliminates LR conflicts? If yes how this happens? Or in other words, how LL conflicts are mapped to LR conflicts? (I believe there should have some minimum connection between LL conflicts and LR conflicts, shouldnt there be?)</p> </blockquote> https://cs.stackexchange.com/q/111006 3 Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD? xskxzr https://cs.stackexchange.com/users/83244 2019-06-21T07:11:33Z 2019-06-21T20:04:49Z <p>In <a href="https://en.wikipedia.org/wiki/Kuroda_normal_form" rel="nofollow noreferrer">Wikipedia</a> of Kuroda normal form, it says</p> <blockquote> <p>A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD. </p> </blockquote> <p>Why are four rules needed here? Aren't three rules: AB → AZ, AZ → CZ, CZ → CD enough?</p>