# Tag Info

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.

2

You can prove inductively that any word $w$ generated by your grammar satisfies $$\#_b(w) + \#_c(w) = \#_a(w) + 1.$$ Also, you can prove inductively that for every $n$, your grammar generates a word having $a^n$ as a prefix. You can now use the pumping lemma to show that the language generated by your grammar isn't regular. Variant: intersect the language ...

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

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

1

Yes, you can. As Dmitry explains, CYK parsing can be used to parse a linear grammar in $O(n^2)$ time, where $n$ is the length of the input word. CYK parsing is a dynamic programming algorithm that sets $P[l,s,R]$ to be true if $a_{s .. s+l-1}$ can be generated from the non-terminal $R$, where $a_{1..n}$ is the input word. Note that there is a recurrence ...

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