# Tag Info

18

No. If a language is context-free, it has a BNF grammar, by definition. A context-free language is a language with a context-free grammar, and a context-free grammar is a grammar written in BNF with only one symbol on the left-hand side of each production. That's what "context-free" means. It might not be convenient to write the grammar. For ...

7

There is an example, and $L = \{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\}$ does the trick. We get that $\sqrt{L} = \{a^nb^na^n \mid n \in \mathbb{N}\}$, which is a standard example of a non-context-free language. To elaborate a bit on how to get there: CFLs can express that two numbers are the same, but not that three numbers are the same. So I want the ...

7

StatementExpression is described in the same specification document as Expression Statements. I would like to quote this passage specifically: Certain kinds of expressions may be used as statements by following them with semicolons. ExpressionStatement: StatementExpression ; StatementExpression: Assignment PreIncrementExpression ...

6

Edit: previously incorrect. Chapter 18 does not have the correct definition of StatementExpression. The correct definition can be found in 14.8. StatementExpression is a subset of the expression grammar. Justification for statement expression: In java, the statement 1 + 1; is invalid grammatically (unlike most other languages).

4

Yuval's answer is absolutely right, but note that there's a more general principle in play here as well: diagonalization. Any time we have a class of decidable languages for which we have a "decidable syntactic description" (I'm being vague about this for a moment), we can diagonalize out of this class to get a decidable language not in the class. ...

4

First, figure out what the language is. Then, try to do a few examples of productions in the grammar. What do you notice about the derivation trees and sequences? How would this help you to prove this grammar is unambiguous? Hint: At each step in the process of deriving a word, what are the possible derivation rules you can use? How would each of them affect ...

2

What he wants to show here is that for any sentence of some given length, there is a (very large but finite) number $m$ which is the maximum number of steps in a derivation of the sentence. If that is true (which it is), then we can figure out whether or not a sentence is generated by the grammar by enumerating all possible derivations with at most $m$ steps....

2

I would approach this question in this way, (k) in $\mathrm{LL}(k)$ means the number of lookaheads. The grammar of $\mathrm{L}$ here possess non-determinism. For example, if you can only see aaaa then by just looking at the first k symbols, you can't make the decision whether it is aaaa or aaaabbbb. No matter how large the value of k is, there will always be ...

2

Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language $$\{ a^n b^n : n \ge 0 \} \cup \{ a^n c^n : n \ge 0 \}$$ is not $\mathrm{LL}(k)$ for any $k$ (see page 246). Presumably a similar proof will show that your language is not $\mathrm{LL}(k)$ for any $k$. You mention a confusion between grammars and ...

1

Languages which can be described by a type 1 grammar are known as context-sensitive. This class of languages is known to coincide with $\mathsf{NSPACE}(O(n))$, the class of languages which can be accepted by a nondeterministic Turing machine using linear space. The space hierarchy theorem gives an example of a computable language which is not context-...

1

If you are trying to convert the grammer into Chomsky Normal Form, consider applying this algorithm that can create a new normal grammer from an existing non-normal one.

1

The main observation is that every word generated by $Y$ starts with $b$. Consider a word $w$. If it starts with $a$, it must have resulted by applying the rule $X \to aX$. Otherwise, it must have resulted by applying the rule $X \to Y$. In other words, if $w = a^n b z$, then the derivation must start by applying $n$ many times the rule $X \to aX$, and then ...

1

Are you aiming to simply allow recursive functions or specify only recursive functions. The following grammar allows recursive functions: function := id '(' parameter ')' '=' function_body ; function_body := conditional | expression ; expression := function_call | <other expression types> ...

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