# Tag Info

13

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: either a finite path through the automaton: words that are shorter than the pumping length; or a path that goes through a node at which there is a loop, in ...

11

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}$, $L_2 \in \mathrm{CFL}$ : $L_1 \cap L_2 \in \mathrm{CFL}$. The first makes a statement on two sets of languages (aka language classes), the second makes one ...

8

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, any context-free language is in $\mathbf{P}$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ . $... 8 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, the "context" part is the idea that certain rules can be extended to apply based on relative positions of symbols rather than on single specific symbols. ... 8 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 that are not inside a Context free language. The trivial example is where the regular language is all strings$\Sigma^*$and the CFL is any other language. The ... 6 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 structure is linear, and for every long word there is a state that is repeated twice in the accepting computation of a finite state automaton. The string read between ... 6 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 relation$V \rightarrow (V \cup \Sigma)^*$- the star covers all productions of the form$A \rightarrow \epsilon$; in all other contexts, it can be omitted because ... 6 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: A → BC, or A → a, or S → ε, where S is the start symbol. Consider the grammar S → TU S → UT T → a U → a Is this a valid context-free grammar in Chomsky Normal Form? Yes, it is. Each rule is of one of ... 5 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.$\forall w, \mathcal M$accepts$w\iff w\in\mathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't ... 5 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 regular expressions is NP-complete; see for example this paper, which discusses efficient algorithms in some special cases. 4 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". A language is recursive if there is some Turing machine that decides it. 4 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 function if it can be computed by a total Turing machine which has a primitive recursive time upper bound. In particular, every language accepted by an LBA is ... 4 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 be a path in which one of the nonterminals repeats. This will allow us to "pump" part of the word, by a cut and paste process. As an example, consider the ... 4 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 when defining the formal syntax of context-free grammars. Either we ask that$\epsilon \notin \Sigma$, or we encode$\epsilon$-rules as$A \to$rather than as$A ...

4

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 or an EXPTIME RAM machine.

4

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 signature $\Sigma$, then a logic $L'$ over signature $\Sigma' \supseteq \Sigma$ is a conservative extension of $L$ provided every $\Sigma$-formula $\phi$ that is ...

3

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 recognized by finite state machines. So it would seem the common usage of "regular language" today traces back to Kleene's "regulary events" rather than to Chomsky's "...

3

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 constant. Deterministic context-free languages (which are those used in practice) can be parsed in linear time. Context-sensitive languages are identical to the ...

3

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.

3

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 a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function. Note that the crux here is repetitions. Since you ...

3

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 exist tasks which take linear space and polynomial time. On the other hand, that doesn't mean every task that takes linear space takes only polynomial time. ...

2

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 you the answer to the original question. Here, you're asking "If a language is RE, are all its subsets?" One of the simplest RE languages we can try is $\... 2 No, it is not true that every subset of a recursively enumerable (RE) language is also RE. In fact, it make sense to say that a subset of a RE language is not RE more often than not. For an example, let us consider the RE language,$\Sigma^*$that contains all words. It is the language of the Turing machine which always halts and accepts in its first step. ... 2 The comment of @Yuval tells the intuition behind the answer (the shortcoming of a PDA is that you can iterate only once over the word and you cannot read the second letter in the stack before popping the first one, note that you can keep only constant amount of data in the state). However, a very concise formal proof why we can not simulate all Turing ... 1 The language$A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$is not obviously regular since finite automata do not have memory and hence it is not possible for them to determine the relation between$a$and$c$. Let us try to construct a Type-2 grammar for this language. Note that Type-2 grammars are of the form$V\to(V \cup T)^{*}$where$V$... 1 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 "the structure of mathematics" could be understood as mathematical structures or as a philosophical term whose definition is up in the air in everybody's mind. ... 1 No. The grammar is defined like this: G = (V,SIGMA, R, S) where V is your set of variables (non-terminals) and SIGMA is your alphabet (terminals). All the symbols you are allowed to use in the substitution of a rule are the union of V and SIGMA. If you simply cannot use a symbol out of that set, since it does not exists in the context of your grammar. 1 The first step is to show that $$L \cap (aac)^*aabb^* = \{ (aac)^n aab b^n : n \geq 0 \}.$$ Given that, you argue as follows: If$L$were regular, then$L \cap (aac)^*aabb^*$would also be regular. You can show in various ways that$\{ (aac)^n aab b^n : n \geq 0 \}$isn't regular. It follows that$L$isn't regular. 1 The definition you state is for noncontracting grammars, which define the context-sensitive languages (modulo the issue of the empty word). In contrast, context-free grammars define the context-free languages, which are a strict subset of the context-sensitive languages. So whoever told you that a Type 1 grammar is context-free iff it is noncontracting, ... 1 A word like$a^nb^nc^n$should work. Remember that the pumping lemma also allows you to pump down, i.e., delete the pumping segments. Also, each splitting$z=uvxyz$can have its own "contradiction" to show it does not adhere to the pumping lemma. You can use different arguments, so different$i$for each splitting. That is very natural here as$a\$ has the ...

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