New answers tagged

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