Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

8

Here is a simple counter example: $S \rightarrow aSbSaSbS \space |\space \epsilon$ and string $w: abababab.$ In one case we use last $S$ and in other case we use second $S$. All other $S$ goes to $\epsilon$. Why I was able to get this grammar? Let's rewrite above grammar with numbers assigned to each $S$'s. $S \rightarrow aS_1bS_2aS_3bS_4 | \epsilon$ ...

5

Unfortunately, your conjecture is wrong. For instance $S \rightarrow aSSb | \epsilon$ is ambiguous. To see that take $w: aabb$. For this string we have following two distinct derivation tree possible. In following derivation trees $e$ represents $\epsilon$ S S / / | \ / / | \ a S S b ...

5

The problem is likely hard, by reduction from SAT. Let $\varphi$ be a CNF. For each clause $C$, we can construct a production which generates all truth assignments falsifying $C$. By going over all clauses, we can construct a grammar for all nonsatisfying truth assignments. For example, if the CNF is $(x_1 \lor x_2) \land (\lnot x_1 \lor x_3)$, the grammar ...

4

If the grammar is ambiguous, then the problem is NP-hard in general, as Yuval Filmus showed, so you should not expect any efficient algorithm. If the grammar is unambiguous, and the corresponding context-free language is finite, then there is an efficient algorithm to find the $i$th word in the language. I'll describe it below. First, note that you can ...

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 ...

3

You could use the digits $\{0,\dots,9\} =: \Sigma$ as alphabet and consider infinite words. A word corresponds then to a real number. Those are known as $\omega$ languages link. There are omega-regular languages too. Edit: The set of all real numbers, $\Sigma^\omega$, forms an $\omega$-regular language of course.

3

Usually, grammar systems where the rules have to be applied in parallel, are called L systems, after the theoretical biologist Aristid Lindenmayer who observed that development in plants must change cells in parallel. The first example at wikipedia has rules : (A → AB), (B → A), and the string (= line of cells) develop as follows: A → AB → ABA → ABAAB → ...

3

Let $L = \{a^n b^n : n \in \mathbb N\}$. Your language can be written as $a^+L \cup Lb^+$, and this leads to the following grammar: \begin{align} &S \to AT \mid TB \\ &T \to aTb \mid \epsilon \\ &A \to aA \mid a \\ &B \to bB \mid b \end{align} We can save a nonterminal by factoring $L$ differently: $$L = \{a^na^mb^n : n \geq 0, m \geq ... 3 This is about the n'th derivation. If the grammar is not unique, and you want the n'th string in the grammar (with duplicates removed), that would be an awful lot harder. As Yuval shows, that would actually make the problem NP-hard. For every symbol, calculate how many sentences can be derived in one step, two steps, three steps etc. Then we define some ... 2 Our grammar G has following two production where S is start symbol. S\rightarrow aTbS \vert\epsilon T\rightarrow aTb|\epsilon Now to convert it to chomsky normal form (CNF) we have to perform following steps: If there is some production having S in it's right side(S\rightarrow aTbS in this example) then add new start symbol S_0 and ... 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 ... 2 We say that \alpha \Rightarrow^* \beta if \beta can be derived from \alpha in zero or more steps. (More fancily, \Rightarrow^* is the reflexive-transitive closure of \Rightarrow.) In particular, it is always that case that \alpha \Rightarrow^* \alpha, for every \alpha, due to a derivation of zero steps. In contrast, in your case it doesn't ... 1 Why is it not possible to have the set of reals in terminal symbols? Because you'd have to list ALL of them, and there an infinite number of reals. However, we can (and do) build the reals themselves out of finite symbols, so we merely regress to having the reals constructed. Before we consider whether the reals can be expressed as a formal language, ... 1 Answer to the last question of the update. The grammar S \to aSb + 1 is linear, but it generates the nonregular language \{a^nb^n \mid n \geqslant 0\}. Therefore, it cannot be converted into a regular linear grammar. 1 The simple way of seeing this class of ambiguities is to observe that if two right-hand sides for the same non-terminal overlap, then they could be applied in either order: D ::= "*" D | D "[" number "]" The overlap is pretty clear: "*" D "[" number "]" Another example, where a right-hand side can overlap with itself: E ::= E "+" E ... 1 Your request is easily served!$$\begin{array}{lcl} &S &\to &abab\\ &ba &\to &bbBa\\ &Ba &\to &aB\\ &Bb &\to &bb\\ &ba &\to &bAaa\\ &bA &\to &Ab\\ &aA &\to &aa\\ \end{array}   There is some theory to help you make sense of this solution. Let ...

Only top voted, non community-wiki answers of a minimum length are eligible