Questions tagged [chomsky-hierarchy]

The Chomsky Hierarchy is the model proposed by Noam Chomsky in 1956 for classes of Formal Grammars. They refer to Type-0, Type-1, Type-2 and Type-3 grammars which refer to Unrestricted Grammars, Content Sensitive Grammars, Context Free Grammars and Regular Grammars.

Filter by
Sorted by
Tagged with
1
vote
1answer
80 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: 𝑆 β†’ π‘Žπ‘† | π‘Žπ‘… 𝑅 β†’ 𝑏𝑅 | 𝑏𝑇 𝑇 β†’ 𝑐𝑇...
3
votes
1answer
553 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), ...
5
votes
1answer
400 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 ...
2
votes
1answer
49 views

Two-way finite automaton: How does the automaton remember the state

I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Ξ£, Ξ΄, q1, F). the 2-DFA B = (Q βˆͺ Q| βˆͺ Q|| βˆͺ {q0, qN, qF}, Ξ£ βˆͺ {#...