# Tag Info

2

More generally, you can use Myhill–Nerode to prove the following characterization: For $A \subseteq \mathbb{N}$, let $L(A) = \{ a^n : n \in A \}$. The language $L(A)$ is regular iff $A$ is eventually periodic. In particular, if $A$ is an infinite set with density zero then $L(A)$ is not regular. Here density zero means: $$\lim_{n\to\infty} \frac{|A \cap \{... 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. ... 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-... 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 ... 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. 0 You can always write a grammar without \lambda, unless the language itself includes \lambda. In that case, you will need the single production S\to\lambda (where S is the start symbol). There's a simple algorithm for removing \lambda from grammars. First, figure out which non-terminals might produce \lambda. (These non-terminals are called "... 0 The given grammar is:$$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$Now the algorithm for the removal of null productions is as follows: We need to find all the nullable symbols from the grammar. A nullable symbol is one that generates the null string in one or more steps. Since A \rightarrow \epsilon so the symbol A is ... 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 ... 0 This language is not context-free, therefore it does not have a CFG. This can be proven using the pumping lemma: suppose L is context-free and let n be the constant of the pumping lemma, and u = a^2bc^{2n}d^ne^{2n}\in L. Using the pumping lemma, we can write u = vwxyz with: wy\neq \varepsilon; |wxy| < n; \forall k\in \mathbb{N}, vw^kxy^kz\in ... 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 ... 0 Let's try to simplify your grammar. First, notice that A generates (00)^*11S, and so we can get rid of A, obtaining$$ S \to 1(00)^*11S \mid 01S \mid \lambda $$Similar reasoning shows that your grammar generates the language$$ (1(00)^*11+01)^* = ((1(00)^*1+0)1)^*,  which is identical to your regular expression. While the reasoning above is informal,...

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

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

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

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

Top 50 recent answers are included