13 votes
Accepted

Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?

Both pumping lemmas have an intuitive explanation in terms of an automaton that can recognize a language. A regular language can be recognized by a finite automaton. All words are recognized through: ...
Gilles 'SO- stop being evil''s user avatar
11 votes

How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

You are confusing two different statements. $\mathrm{CFL} \cap \mathrm{REG} = \mathrm{REG}$ or, equivalently, for all $L_1 \in \mathrm{REG}$ : $L_1 \in \mathrm{CFL}$. For all $L_1 \in \mathrm{REG}$, ...
Raphael's user avatar
  • 72.4k
8 votes
Accepted

How did each class of languages receive their name?

Regular Languages: There's some good discussion of this here: https://ell.stackexchange.com/questions/83917/how-did-regex-get-its-name Context-Free vs Context-Sensitive Grammars: For CFGs and CSGs, ...
mdxn's user avatar
  • 1,301
8 votes
Accepted

How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

No, you are misinterpreting stuff. The set of languages (DFL, regular, ...) and the set of strings in a language are independent. It is entirely possible that a regular language contains strings ...
ratchet freak's user avatar
8 votes
Accepted

Chomsky Hierarchy and P vs NP

Regular languages Regular languages are in $\mathbf{P}$ because a deterministic finite automaton is a restricted deterministic Turing machine that runs in linear time. Context-free languages In fact, ...
David Richerby's user avatar
7 votes
Accepted

Is the empty string a terminal symbol?

It's true that, in general, definitions don't include the empty string in the set of "terminals", as there's no need for that (e.g. the production rules for a context-free grammar are defined as a ...
potestasity's user avatar
6 votes

Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?

That is because of the "structure" of the languages that is observed by the respective pumping lemma's. Have a look at the proofs of the respective pumping results. For regular languages the ...
Hendrik Jan's user avatar
  • 30.6k
6 votes
Accepted

Converting context-free grammar to chomsky normal form

You're right to be cautious, but there is nothing wrong. A context-free grammar is in Chomsky Normal Form if and only if every rule is of the form: ...
reinierpost's user avatar
  • 5,519
6 votes
Accepted

Where can we put primitive recursive functions in Chomsky hierarchy?

The Chomsky hierarchy concerns languages. Languages are total functions from $\Sigma^*$ to $\{0,1\}$, where $\Sigma$ is some non-empty finite set. A language can be computed by a primitive recursive ...
Yuval Filmus's user avatar
5 votes

Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

A language $\mathcal L$ is recursive if there exists a Turing machine $\mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $\mathcal L$ (i.e. $\...
wazdra's user avatar
  • 362
5 votes

Is the empty string a terminal symbol?

The empty string is not a terminal symbol. A terminal symbol is an element of the alphabet, but the empty string is not an element of the alphabet. In fact, this is an issue that we have to address ...
Yuval Filmus's user avatar
5 votes
Accepted

What problems are solvable in Datalog?

According to these slides, deciding whether a single atom is generated by a Datalog program is EXPTIME-complete. There are several corresponding machine models, for example an EXPTIME Turing machine ...
Yuval Filmus's user avatar
5 votes
Accepted

When did "regular" start referring to Type 3 languages/grammars?

I found an answer, at least a partial one, hinted at in Footnote 10 of Chomsky's paper where he refers to a 1956 paper by Kleene in which Kleene describes "regular events" -- a language ...
cristoper's user avatar
  • 181
5 votes
Accepted

What is the computational complexity of "real-life" regular expressions?

The following extended regular expression matches the language $\{ ww : w \in \Sigma^* \}$: $$ \texttt{^\\(.*\\)\\1\\\$} $$ This language is neither regular nor context-free. Matching using extended ...
Yuval Filmus's user avatar
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

Expressive power of formal systems

Comparison of logics is a complicated subject. Expressive power of logics can be 'measured' in various ways. The most well-known approach is that of conservative extensions. If $L$ is a logic with ...
Martin Berger's user avatar
4 votes

Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

a language A that is recursive for some Turing Machine That's your problem, right there. A language is either recursive or it's not: there's no such thing as "recursive for a specific Turing machine"....
David Richerby's user avatar
4 votes

Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?

The pumping lemma for context-free languages is, at heart, an application of the pigeonhole principle. If we take any long enough word in the language and consider one of its parse trees, there will ...
Yuval Filmus's user avatar
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 mathematics context-free?

Let me quote the question. Can the structure of mathematics, as represented by ZFC (or perhaps the Peano axioms), be represented as a context-free language? I would like to clarify that the phrase ...
John L.'s user avatar
  • 39k
3 votes
Accepted

Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?

It is not possible: it is undecidable whether a context-free grammar describes a regular language. For a proof, see e.g. Undecidable Problems for Context-free Grammars by Hendrik-Jan Hoogeboom.
reinierpost's user avatar
  • 5,519
3 votes
Accepted

What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?

Regular languages can be accepted in linear time and constant space. Valiant's algorithm parses arbitrary context-free languages in time $O(n^\omega)$, where $\omega$ is the matrix multiplication ...
Yuval Filmus's user avatar
3 votes

Are Context Sensitive Grammar with Polynomial Complexity Time?

To your first question, the answer is affirmative: On one hand, a task that only takes polynomial time can only take polynomial space, and many among them only take linear space, so there definitely ...
reinierpost's user avatar
  • 5,519
3 votes

Is every subset of a RE language also RE, in general?

The trick to answering questions like this is to start by considering cases that make the question as simple as possible. If you're lucky, the simplified question will be easy to answer and will give ...
David Richerby's user avatar
3 votes
Accepted

What is known about the sets enumerated by primitive recursive functions?

In "Extensions of some theorems of Gödel and Church" it's shown by Barkley Rosser that these sets are exactly the recursive sets: Corollary I. If a class can be enumerated (allowing repetitions) by ...
orlp's user avatar
  • 13.4k
3 votes
Accepted

CYK algorithm in theory of computation

It's true. If the CFG is not null free, and the input sentence is not null, you can remove the null from the CFG and then parse the input sentence with the resulting grammar. You already know how to ...
D.W.'s user avatar
  • 159k
3 votes

Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar

All of the grammars in your first figure are context-free grammars. That text seems to identify grammar with context-free grammar.
Yuval Filmus's user avatar
3 votes
Accepted

Prove/find context free grammar is unambiguous for the language $L$

Your updated grammar is SLR(1) which can be seen there, thus unambiguous, but constructing SLR-parsing tables is not an elegant way to prove things. If you use the following grammar form (which is ...
Tonita's user avatar
  • 565
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

Why do type-3/regular languages require a terminal symbol on the right-hand side?

it would be guaranteed to finish parsing in exactly the number of “steps” (instances of re-writing) as there were non-terminal symbols in an input string. There are no non-terminal symbols in an ...
confusedcius's user avatar

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