9
All of these (except possibly Kleene closure) are answered (in the negative) in Rosenkrantz & Stearns, Properties of Deterministic Top-Down Grammars, 1970.
For an example of a language whose Kleene closure is non-deterministic, see this answer by Hendrik Jan.
4
One endmarker is insufficient to prove this. Instead, we must use multiple endmarkers. Here's the full proof, with the same basic idea taken from the other answer.
Using the notation from Sipser 3rd edition problem 5.21, let the string pairs $(t_i, b_i)$ for $i \in \{1, 2 \ldots k\}$ be an instance of the PCP problem. Define grammar rules $T \rightarrow t_i ...
3
I don't think there is a widely-used formal definition, and that this is so for a good reason. Sub-problems or sub-instances are tools used in the process of designing algorithms (for "divide and conquer" or "dynamic programming" in particular, but also more generally).
The process of (humans) designing algorithms is not a completely ...
3
I have also not seen a formal definition, and I have seen subinstance and subproblem used interchangeably, but also seem to remember some people separating them (and can find no evidence to support this).
The closest things I have found to a definition on hand:
Subinstances: From the original instance, construct one or more subinstances, which are smaller ...
3
Not that I know of. But see here for some common patterns in dynamic programming algorithms: What is dynamic programming about?.
3
The Stanford Encyclopaedia of Philosophy has a summary of the history of recursive functions. In particular, in Section 1.8 we can read that Stephen Kleene explicitly defined the partial recursive functions, and showed them to be equivalent to several other notions of computable functions, in a series of papers between 1936 and 1954. For example, already his ...
2
Yes, here the idea of one with three states. I don't know stuff formally enough to write tuples.
Keep track of the parity of 'a's you read in two states.
If you read 'aa', push A on the stack
When you hit b, you better be on odd parity
Pop 'A' for every 'b' you read
At the end of the input, succeed if the stack is exactly empty.
This accepts only when i == ...
2
The idiom "$X \to YX \mid \epsilon$" (or "$X \to XY \mid \epsilon$") means that $X$ generates $Y^*$ (assuming there are no other productions for $X$). This means that your grammar generates $A^*$. You know what $A$ generates. Putting everything together, you should be able to find a very concise description of the language generated by ...
2
To add to the other good answers already here consider how subinstances are used in practice. Given an instance (formally a string $x$) we construct another instance (this too we could formally describe as a string $y$). This new string representing our subinstance is the output of some (computable) function of the original instance (We could say $y = f(x)$ ...
2
What your argument actually shows is
$$
L = L^* \Rightarrow L=L^2 \Rightarrow L = L^+.
$$
Indeed, suppose that $L = L^*$. On the one hand, $L^2 \subseteq L^* = L$. On the other hand, since $\epsilon \in L$, we have $L = \epsilon L \subseteq L^2$.
Next, suppose that $L = L^2$. Inductively, $L = L^n$. In particular, if $w \in L^+$ then $w \in L^n$ for some $n$,...
1
They are different, because:
$(a \cdot b)^2 = abab$, since you need to concatenate $a$ and $b$ first, them reapeat the concatenation two times.
$a^2 \cdot b^2 = aabb$, since you need to concatenate the repetition of two $a$ with the repetition of two $b$.
1
Just as a slight nit, those aren't $LR(1)$ item sets, because they don't include the following terminal symbol
With that proviso, your reasoning looks good to me. Of course, the language is not inherently nondeterministic because you can rewrite $B$ as:
$$B \rightarrow \epsilon\,|\,Bbb$$
The palindrome language $L = \left\{ w w^R\,|\,w \in \Sigma^* \right\}, ...
1
Eliminating right-recursion can create parsing conflicts in an LALR(k) grammar.
Here's a very simple example with $k=1$.
$$\begin{align}S&\to L R\\
L&\to \epsilon\\
L&\to L a b\\
R&\to \epsilon\\
R&\to a c R\\
\end{align}$$
That grammar is LALR(1). If you change R to left recursive:
$$\begin{align}S&\to L R\\
L&\to \epsilon\\
L&...
1
The answer to your first question is: Not that we know of.
A grammar is $\hbox{LALR}(k)$ if and only if its $\hbox{LALR}(k)$ automaton is deterministic. The only way that we know of checking that a grammar is $\hbox{LALR}(k)$ is to build the automaton, or something that essentially amounts to building the automaton.
The good news is that the key complication ...
1
Producing sentences from a formal grammar does not require a Linear Bounded Automaton (LBA) and does not use a stack. LBAs are an interesting field of investigation but in terms of this question they are mostly a distraction.
Generative or formal grammars do not actually need much in the way of specialised knowledge to understand, at least in terms of what ...
1
Your understanding of Linear Bounded Automata is incorrect. These automata are NOT derived from Pushdown Automata - there is no 'stack' in them. A closer understanding would be that LBA are a special, 'truncated' form of Turing Machine, in which the size of the tape is restricted to being linearly-proportional to the size of the input string (actually, ...
Only top voted, non community-wiki answers of a minimum length are eligible
