21 votes
Accepted

How do C compilers distinguish casting from grouping?

It's not possible for an LR(1) parser to solve this problem without using the Lexer Hack: information from the symbol table, which is able to differentiate type names from variable names, is reported ...
Scott McPeak's user avatar
17 votes
Accepted

Is a machine Turing-complete when it can decide a context-sensitive language?

No. Context-sensitive languages can be recognized by linear-time nondeterministic Turing machines, which are not Turing complete. The ability to recognize a recursively enumerable set also does not ...
D.W.'s user avatar
  • 159k
16 votes
Accepted

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Sipser clearly implies an or between those two rules. The two definitions say the same thing. Meanwhile, in formal language theory, it is quite common for two textbooks or article to not say the same ...
reinierpost's user avatar
  • 5,519
12 votes

How do C compilers distinguish casting from grouping?

They can easily be distinguished by a compiler: In the first case, the thing in parentheses is a type, in the second case it isn’t. Now if you insist on parsing based on a grammar only, that may be a ...
gnasher729's user avatar
8 votes

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Sipser doesn't require that both of those forms be used. It just requires that every rule fit one of those two patterns.
D.W.'s user avatar
  • 159k
5 votes
Accepted

Repeated rules with more than three symbols for conversion to Chomskys Normal Form

Yes, if the same strings are generated the productions can be shared. The "standard" conversion does not consider such "coincidences". Note that your final result does not yet ...
Hendrik Jan's user avatar
  • 30.6k
4 votes

What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

I believe that the questioner is inquiring about the Church-Turing thesis.
mhum's user avatar
  • 2,092
3 votes
Accepted

Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

It seems you almost solved the problem in your question statement. Note that the $n\neq m$ condition makes pumping hard: one needs a trick using factorials to succeed, see Prove if $L=\{0^m1^n∣m≠n\}$...
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

CFG {$w\in ${a,b,c}$^* | $#$_a(w) + $#$_b(w) = $#$_c(w)$}

You are interested in the language $L = \{w\in \{a,b,c\}^∗\mid \#_a(w)+ \#_b(w)= \#_c(w) \}$ but question how to haave the symbols in arbitrary order. You have solved $\{w\in \{a,b\}^∗\mid \#_a(w)=...
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?

Whether 2-bracket Dyck is equivalent to $n$-bracket Dyck ($n\ge2$)? Short answer: that depends which operations one allows. The Chomsky–Schützenberger Theorem states that every context-free language $...
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

Language of equal numbers of as, bs, cs in any order not context-sensitive?

It seems the author of the book is a little careless at this point. His definition of context-sensitive is that "the right-hand side of a rule must never be shorter than the left-hand side" ...
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Basically, the idea is that $($ and $)$ can commute with $[$ and $]$, but $($ cannot commute with $)$ – and same for $[$ and $]$. An essentially noncontracting grammar would be: $S \to \varepsilon \...
Nathaniel's user avatar
  • 15.4k
2 votes

Equivalence of LR(k) and LL(k′) parsers

Yes, $\{a^i b^j c \mid i \ge j \ge 0\}$ can be parsed by a $LR(0)$ parser but not by any $LL(k')$ parser for any $k'$. See How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?. See also ...
D.W.'s user avatar
  • 159k
2 votes

What's really meant by context-free in the term context-free grammar?

What's meant by "Context Free"? Ultimately that the applicability of a phrase structure rule, for a grammar, should be independent of the surrounding context, where it is applied. The fact ...
NinjaDarth's user avatar
2 votes
Accepted

Is { a^nb^na^n} a context-sensitive language?

The grammar: $S\to aS'Ba\mid aba \mid\varepsilon$ $S'\to aS'Ba\mid aba$ (so that only the start symbol can generate the empty word) $aB \to Ba$ (to move the inner $a$'s to the right) $bB \to bb$ (to ...
Nathaniel's user avatar
  • 15.4k
2 votes
Accepted

An elementary question about grammar

You are close, but not precise. Usually one distinguishes between the arrow notation for the rules $A \to aA$ and the notation for derivation in the grammar, that is the application of the rules in ...
Hendrik Jan's user avatar
  • 30.6k
2 votes
Accepted

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Intuitively you cannot check palindromicity and (un)equality of numbers using a single pushdown, so also $P'$ must be non-context-free. Formally proving unequal-repeating-numbers to be non-context-...
Hendrik Jan's user avatar
  • 30.6k
2 votes
Accepted

Is the class of star-free languages just the complement to counter languages within the regular language class?

These languages families are related by similar names only, both formalisms have their own relation to the concept of counting. The beauty of regular languages is that they can be defined using (...
Hendrik Jan's user avatar
  • 30.6k
2 votes
Accepted

How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Take a look at $$L = \{a^nb^nc^ma^mb^kc^l : n, m, k, l \geq 0\}.$$ Now take some $x \in L$ with $x = ww$, then $x = a^nb^nc^ma^mb^kc^l$ for some $n, m, k, l \geq 0$. There's only one possible way to ...
Knogger's user avatar
  • 1,032
2 votes
Accepted

Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

The problem with your (new) solution is that you force $n$ to be equal to $3m$. That means that your grammar generates words that are in $L = \{a^nb^m\mid 2m < n < 4m\}$, but words in $L$ like $...
Nathaniel's user avatar
  • 15.4k
1 vote

Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

No. The grammar you propose is not correct. For example it generates $\varepsilon$, which is not in the language. In fact, no word generated by your grammar is in the language. To see this notice that ...
Steven's user avatar
  • 29.4k
1 vote

How are PCFGs used in programming language design?

I am not aware of applications in programming language design, and I am a bit skeptical. However, PCFGs are useful for generating test cases, for program testing.
D.W.'s user avatar
  • 159k
1 vote

What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

In my recent question, I asked why do we consider Turing Machines as a limit of computation, you can check it here, good answer was provided for it: Is the Turing machine the only framework to analyse ...
math boy's user avatar
  • 353
1 vote
Accepted

What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

The term I was looking for, that collects research on my original question as to whether there was a proof that Turing completeness is the most powerful model of computing, is hypercomputation: https:/...
Luke Hutchison's user avatar
1 vote

How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Context-free languages are not closed under intersection. We start there. The relevant example is here that $\{ a^p b^p c^q \mid p,q\ge 0 \} \cap \{ a^p b^q c^q \mid p,q\ge 0 \} = K$, where $K = \{ a^...
Hendrik Jan's user avatar
  • 30.6k
1 vote

Trouble proving this is regular

Note that for two ternary numbers $x = x_1x_2...x_n$ and $y = y_1y_2...y_n$ with digits $x_i$ and $y_i$ holds that $$x < y \iff x_1x_2...x_n \prec y_1y_2...y_n$$ where $\prec$ is supposed to be the ...
Knogger's user avatar
  • 1,032
1 vote

Communication complexity of Dyck language

TL;DR: $n \le C(f) \le n+1$. We can easily prove that $C(f) \ge n$. Consider the set of $x \in \{(,[\}^n$. There are $2^n$ such $x$-values. Each matches a different set of $y$-values. So, you need ...
D.W.'s user avatar
  • 159k
1 vote

Derivation trees to show a given grammar is ambiguous

I believe your professor is wrong. You exhibited two leftmost derivations, which is all that is required to show a grammar is ambiguous. Although, one small thing: $S \Rightarrow SS \Rightarrow aSbS \...
Dair's user avatar
  • 232
1 vote
Accepted

Is $L=\{1^n2^n3^m : n\neq m\}$ context free?

The language is not context free, and indeed Ogden's Lemma can be used to show so. See the answer in the following duplicate.
oleshkowitz's user avatar
1 vote

How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?

I think the language is indeed context-sensitive. Here is a non-contracting grammar generating it. $S \to A' \mid B' \mid aS' \mid \varepsilon$ $A' \to aA' \mid a$ (in the case there is no $b$'s, ...
Nathaniel's user avatar
  • 15.4k

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