The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [chomsky-hierarchy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
0answers
45 views

Does type-1 lambda calculus exist?

I'm interested in the intersection of linguistics and computer science, I've been reading on Chomsky hierarchy, and would like to know if there exist lambda calculus types that are equivalent to the ...
1
vote
2answers
38 views

Doubt regarding Chomsky Hierarchy, CFG and CSG

I was following a discussion on a website, where a fellow scholar claims that this grammar S→ aAa | bAb | ϵ A→aA | bA |ϵ is not CSG, so it should also NOT be a CFG. But this grammar properly ...
1
vote
1answer
17 views

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

Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is primitive recursively enumerable if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, ...
2
votes
1answer
67 views

Are Context Sensitive Grammar with Polynomial Complexity Time?

Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space. Assuming a Deterministic Parser is the one which can parse unambiguous grammars in ...
0
votes
1answer
104 views

Chomsky Classification of Languages

Given is a language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ ; where $N^{+}$ are the natural numbers excluding 0. I have found a type-1 grammar to describe it: $S \to A_1A_2$ $A_1 \...
1
vote
2answers
169 views

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

I'm trying to understand the question in my title in an intuitive way: If I have an RE language A, then some TM, say TM(A) accepts on it. If I take a subset of A, say A2, then all elements of A2 will ...
2
votes
2answers
411 views

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

I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
-3
votes
1answer
280 views

Is mathematics context-free?

Anyone who deals with mathematics knows intuitively that it is a different kind of thinking than ordinary common-sense thinking that intelligent people use every day to understand and make decisions ...
3
votes
1answer
118 views

Where can we put primitive recursive functions in Chomsky hierarchy?

I am currently studying recursion theory, but I cannot really understand where to put the Primitive Recursive functions in the Chomsky hierarchy. In my understanding, Primitive Recursive functions ...
3
votes
1answer
373 views

Chomsky Hierarchy and P vs NP

I have read multiple questions here that involve this kind of subject but I haven't found any definite answer. In what class do regular languages belong? (P or NP or some regular are P and other NP), ...
0
votes
0answers
68 views

Is a Turing Machine able to reduce a grammar by chomsky hierarchy? [duplicate]

If given a grammar, for example, a context-sensitive (type 1) can it always be "reduced" to a equivalent context-free grammar (type 2) and so on for grammars type 2 to "reducing" and getting a type 3? ...
1
vote
1answer
74 views

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

For example: This looks like a context free grammar: 𝑆 → 𝑄𝑅𝑇 𝑄 → 𝑎𝑄 | 𝑎 𝑅 → 𝑏𝑅 | 𝑏 𝑇 → 𝑐𝑇 | c but it can be reduced to this regular language: 𝑆 → 𝑎𝑆 | 𝑎𝑅 𝑅 → 𝑏𝑅 | 𝑏𝑇 𝑇 → 𝑐𝑇...
7
votes
3answers
1k views

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

Basically what the title says. Why can you "ignore" the "xy" part if you want to prove whether a language is regular?
0
votes
1answer
71 views

Type-0 grammar and terminal symbols

The question is pretty short, but I've been thinking about it quite some time: Are terminal symbols that are not in the defined alphabet still valid?
1
vote
1answer
45 views

Decide whether this language is regular

Decide whether the language $L$, defined by the following grammar is regular or not: $S \rightarrow aab$ $S \rightarrow aacSb$ $S \rightarrow acSab$ $S \rightarrow acSacSb$ Where should I start? I ...
0
votes
0answers
76 views

Grammar/Chomsky-Type for $L = \{ww \mid w \in \{a,b\}^*\}$ [duplicate]

I've been given the following task and have tried a few things, but none seem to result in what is required. $L = \{ww \mid w \in \{a,b\}^*\}$ What Chomsky-Type is $L$? Provide a grammar fulfilling ...
2
votes
2answers
1k views

Is the empty string a terminal symbol?

I ask this question with regards to a grammar in Chosmky Normal Form. The definition states that the rules must be of the following forms: A $\rightarrow$ BC A $\rightarrow$ a S $\rightarrow$ $\...
4
votes
2answers
804 views

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

Intersection of CFL and regular is always CFL. But according to Chomsky hierarchy diagram, regular languages lie completely inside CFL. So, as regular set is completely inside CFL set, their ...
3
votes
0answers
134 views

Do Combinational Logic circuits describe a set of languages?

I was looking at this picture: https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/640px-Automata_theory.svg.png Which made me think, that if all Turing Machines PDA's and ...
2
votes
1answer
522 views

How can CFGs have epsilon rules if CSG may not have them?

I am new to theory of computer science and I am currently reading about CTF grammars. In our lecture we defined that a Type 1 grammar is context-free if for $w_1 \to w_2$, $\vert w_1 \vert \leq \vert ...
3
votes
1answer
88 views

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

In his 1959 paper, On Certain Formal Properties of Grammars, Chomsky defined a "regular" grammar as a specific form of a type 2 (context-free) grammar. (See Definition 8 of that paper.) He then goes ...
3
votes
1answer
351 views

Is $L=\{a^ib^jc^k : i\leq j\leq k\}$ context-free?

I have an exam and in preparation I found this language. We are supposed to determine where in Chomsky hierarchy it stands. The language is $L=\{a^ib^jc^k : i\leq j\leq k\}$. I can easily build a ...
6
votes
1answer
236 views

Expressive power of formal systems

How do we classify formal systems' (propositional logic, first-order logic, second-order logic, higher-order logic, Hoare logic and type theory) expressivity? In the same way that grammars (CSG, ...
3
votes
1answer
137 views

How the closure properties of the formal languages dictate decidability of their problem

Consider the following problem: Is $L_1 * L_2$ is of $LType$? where we know that both $L_1$ and $L_2$ are of type $LType$ and $LType$ is closed under $*$ operation. Above, by $LType$, I ...
1
vote
2answers
46 views

Is it possible to eliminate the unit rules in this?

S -> aA | bC | CC | a | b | C A -> B B -> S C -> A | S It looks like its going to loop so it would be endless replacing the unit rule....
5
votes
1answer
334 views

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

Everybody knows the Chomsky-hierarchy for describing formal languages and big-O notation for describing time and space complexity of a function. We know, that each class in the Chomsky-hierarchy ...
1
vote
1answer
65 views

What problems are solvable in Datalog?

Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what ...
2
votes
2answers
10k views

Converting context-free grammar to chomsky normal form

I'm trying to prove that the following CFG can be converted to a CNF: S -> aAB A -> aAa A -> bb B -> a Here below is how I've managed so far: Step 1:...
0
votes
1answer
83 views

Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?

At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the ...
6
votes
1answer
141 views

How did each class of languages receive their name?

If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable ...