New answers tagged

0

Let's start where you probably started, with the classic expression grammar: $$\begin{align}E&\to T\mid E + T\mid E - T\\ T&\to F\mid T * F\mid T / F\\ F&\to ( E )\mid x\\ \end{align}$$ and then we add the "fused" productions: $$\begin{align}E&\to E + T * F\mid E - T * F\\ \end{align}$$ That grammar has a conflict because of the ambiguity:...


2

Your question is very philosophical in nature because you are asking about what is considered by computation and it’s physical implementations. In short, there is a ongoing discussion on different accounts of concrete computation e.g. the simple mapping account, the semantic account, the syntactic account, the mechanistic account, the causal, the ...


2

Starting point: $$ S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b $$ Substitute values of $A,B,E$: $$ S \to aCD \\ C \to bD \mid \varepsilon \\ D \to C \mid b $$ Substitute values of $D$: $$ S \to aCC \mid aCb \\ C \to bC \mid bb \mid \varepsilon $$ You can generate $bb$ from $C$ even without the rule $C \...


2

I think you can solve this using this construct: $$S \rightarrow ASA|BSB|ATA|BTB $$ $$T \rightarrow CAZC|CBZC$$ $$Z \rightarrow AZ|BZ|\epsilon$$ $$A \rightarrow a , B \rightarrow b, C \rightarrow c$$ First rule provides the $w$ and $w^R$ in the language, second rule makes sure $v \ge 1$ and has 1 c in both sides and third is just constructing the $v$ ...


1

I have wondered something similar and failed to find much in the way of satisfying answers in the literature. Here is what I tentatively came up with. It seems perhaps what we need is some kind of regularization. If $\theta$ is a model (say, a regular expression), let $c(\theta)$ denote some measure of the complexity of the model (say, the size of the ...


2

Another way to arrive at a solution here - you might recognize that this language is regular, since, intuitively, you’d only need to remember whether you’d seen zero a’s, one a, or two or more a’s. You can build a very simple two-state NFA for this regular language. The start state corresponds to having seen no a’s. It isn’t accepting and has a self-loop on ...


2

$$S\rightarrow aA, bS,cS$$ $$A\rightarrow bA, cA, \epsilon$$ Note that you need at least two non-terminals for this language, since you need to differentiate two states, namely whether an $a$ has already been added/found or not.


0

Your CFG looks correct, but it can be made simpler. The production $S \rightarrow SAbAbAbAS$ can be replaced by $S \rightarrow SbAbAbA$ (i.e. remove the first $A$ and last $S$) . Given any string containing $3k$ $b$'s $(k \ge 1)$, the suffix of the string starting with the third $b$ from the right can be generated by the $bAbAbA$ part. For example, if ...


1

Useless symbols are those that do not appear in any derivation from the start variable of some terminal string. If you similarly define useless productions to be those productions that are not used in any derivation from the start variable of a terminal string, then observe that the production $B \rightarrow aa$ is useless because $B$ is not reachable from ...


0

Consider where "a" terminals can appear in a string produced by this grammar. Based on that, you should be able to split the "A" nonterminal up to make a right-recursive grammar that matches the same strings. (Also, your "B" nonterminal appears to be missing...? Or just has no productions?)


1

Starting from $S$ it is impossible to generate a sentential form that contains the nonterminal $B$. This is easy to see since: $S$ only has productions whose body contain $S$ itself, $A$ or $C$. $A$ has no nonterminals in the body of its productions. $C$ has only $C$ itself in the body of its productions. This means that the production $B \to aa$ is ...


1

In the context of context-free languages, "top-most" refers to the root of a parse tree. Your rules guarantee that a sum of the form $1+1+1$ is parsed as $1+(1+1)$ rather than the opposite, since the nonterminal Ntp ("not top-most") doesn't allow + to be the top-most operator (you should imagine a parse tree in which + labels the root). Consider the ...


0

$$ \begin{align*} S \to & AbBC \mid AbBCc \mid AbBCcc \; \mid \\ & aAbBC \mid aAbBCc \mid aAbbBCcc \; \mid \\ & aaAbBC \mid aaAbbBCc \mid aaAbbBCcc \\ B \to & bB \mid \epsilon \\ A \to & aaaAb \mid \epsilon \\ C \to & bCccc \mid \epsilon \end{align*} $$ The intuition is as follows: The nonterminal $B$ encodes the fact that we ...


4

You said in a comment: I am talking to process this encoding, not the tape content. But the tape content affects the behavior of the TM, including whether it would enter an accepting state. The exact same TM in the exact same state might later accept, or not accept, depending only on what is on the tape. You want to "go through all encoded transitions ...


2

Because this process doesn't necessarily end; you can end up discovering more and more possible configurations (state+tape) which would lead to accepting if they were ever reached, but never a legal initial configuration.


2

$\#$ here is just a symbol; it has no special significance. (It's often used in the construction of an modified language to indicate a new symbol which is not in the alphabet of the original language.) $\#^{g(x)}$ is, therefore, the unary encoding of $g(x)$; in that sense, it is a count. The double-triangle used in the later proof is just another such ...


Top 50 recent answers are included