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.
67
questions
4
votes
1
answer
342
views
Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?
I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N.
Afaik the Chomsky-Schützenberger representation ...
- 67
-1
votes
1
answer
172
views
Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it
Were w is any string composed over the alphabet $\Sigma = \{0,1\}$.
For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
- 3
0
votes
1
answer
37
views
Find Grammar for L(G) ={a^i b^j c^k | k = i*j ;i, j ≥ 1}
Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i*j ;i, j ≥ 1}
Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to ...
0
votes
0
answers
41
views
Which language can be parsed recursive descent?
We consider languages over the alphabet {a,b,c}. Given a character t in the alphabet and a non-negative integer j, by t^j we mean the string consisting of exactly j occurrences of t.
Now let m be an ...
- 3
0
votes
0
answers
50
views
Removing null production from cfg
While removing null production from cfg as below,
S->ABC
A->aA|^
B->bB|^
C->aaC|^
now as shown above we know that A,B and C all are ...
0
votes
0
answers
32
views
Book recommendation: computability theory and Chomsky hierarchy
What is a good book for learning computability theory that covers the Chomsky hierarchy?
- 123
1
vote
1
answer
38
views
Does Sipser's _Introduction to the Theory of Computation_ cover the Chomsky hierarchy?
I saw the book suggested here.
Does Sipser's Introduction to the Theory of Computation cover the Chomsky hierarchy?
I ask since, looking through a pdf copy of the book, I found no matches with "...
- 123
1
vote
1
answer
71
views
What is a contracting grammar (in opposition to a non-contracting grammar)?
In the Chomsky hierarchy what is corresponding to a contracting grammar?
I can find references to non-contracting grammars (which can be transformed into context-sensitive grammars accordingly to what ...
- 221
0
votes
2
answers
78
views
Example 7.1 correctness in Introduction to Automata Theory, Languages, and Computation
The example says that C is unreachable, but there is the production S-> aBC so C is clearly reachable. This is an error right? or am I missing something.
- 1
1
vote
0
answers
37
views
Which non regular language meets the requirements for pumping lemma for regular languages?
I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
2
votes
1
answer
201
views
Prove/find context free grammar is unambiguous for the language $L$
I am trying to find a grammar and prove that it is unambiguous for the language $L$, where $$L = \{ w \in \{a,b\}^+; |w|_a = |w|_b \} $$
Essentially: word $w$ contains at least one $a$ and $b$; where ...
- 23
1
vote
1
answer
46
views
Which abstract machine or language is exactly expressive enough to produce the computable functions?
I'm interested in software verification and therefore only interested in algorithms which always terminate in predictable amount of time and can determine whether the final result is expected or not, ...
- 165
1
vote
3
answers
118
views
Confused about Turing Recognizability
If Turing Recognizability means a T.M. will either halt on input $w$ if $w$ is in the language, or run forever if $w$ is not in the language.
How can we know the language is Turing Recognizable if we ...
- 11
2
votes
1
answer
98
views
What is the outermost class 2^Σ* referring to on the Extended Chomsky Hierarchy?
After having searched a bit, it seems I can't find terminology or references for this outermost class, 2Σ* in blue -- see below. What is it describing?
- 162
0
votes
1
answer
29
views
What is the subset of CFGs called where each expansion must be the same?
I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
- 103
1
vote
1
answer
118
views
simulate PDA using LBA
urestricted -> turing machine
context-sensitive -> linear bounded automaton (LBA)
context-free -> pushdown automaton (PDA)
regular -> finite state machine
Hi, I am kind of confused ...
- 11
1
vote
1
answer
322
views
Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar
While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below.
The above diagram is very helpful in understanding the correlation among ...
- 1,112
0
votes
0
answers
26
views
Is this a correct Type 1 grammar?
The task was to give a type 1 grammar(can't be of type 2) which accepts the following words:
baaaab, abb, abba(ab)^i for all i ∈ ℕ
and doesn't accept these words: aabb, bba, bbabb(baaa)^i for all i ∈ ...
- 1
1
vote
1
answer
151
views
Easy-to-prove example of non-contextual language
When studying Chomsky's hierarchy of languages (starting from type 3), I find enlightening to encounter some language that can't belong to the current type but which very obviously belong to the next ...
- 131
1
vote
0
answers
42
views
what is the difference between L-system and string re-writing?
I was going through the L-System Wikipedia (https://en.wikipedia.org/wiki/L-system) and it mentions that L-Systems are very similar to unrestricted grammars / string re-writing. After going through ...
- 23
0
votes
0
answers
58
views
Context Free Grammar to Chomsky Normal Form Help
I am trying to convert the following CFG to CNF:
S -> ABS | ε
A -> BSBa | a
B -> Ba | a
The finally result looks like this:
...
0
votes
1
answer
170
views
How to demonstrate unambiguous CFG and CNF?
I have to show that if G is an unambiguous CFG, the transformed grammar G' in CNF is also unambiguous. But couldn't come up with something concrete. I could only visualize the case where the grammar G ...
-2
votes
1
answer
188
views
Finding the language generated by this grammar
I'm having problems with this. Can someone help me please.
Find the language generated by this grammar over the alphabet $\{0,1\}$:
$S\rightarrow BAB\mid CAB$
$BA \rightarrow BC$
$CA \rightarrow AAC$
...
- 3
0
votes
0
answers
58
views
Chomsky Hierarchy of a Computational Model
I am interested in knowing the Chomsky hierarchy of a particular computation model. Also, I would like to know if it is equivalent to Finite State Machine or is Turing complete.
This computation ...
- 101
0
votes
1
answer
69
views
CYK algorithm in theory of computation
For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n.
Doubt: I marked it false in a national level exam.I think it should be any null-free context ...
1
vote
1
answer
53
views
Can a Turing machine or Push Down Automaton construct languages of type 3?
I am not quite sure, whether automata can construct languages over their types. For example, a Push down automaton can construct a language of type 2 - does that mean that a PDA also can construct a ...
- 13
0
votes
1
answer
40
views
How can Chomsky hierarchy be applied to languages with alternated letters?
I have the following grammar, which I know it is regular because it can be represented by a finite state automata:
\begin{array}{l}
\mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\
\mathrm{X} \...
- 103
0
votes
1
answer
278
views
What becomes of context-sensitive grammars if $\epsilon$ productions are allowed?
The original formulation of the 3 restricted grammar types of Chomsky all included the restriction that the right-hand side of a replacement cannot be $\epsilon$ (non-contracting). This, however, can ...
1
vote
0
answers
119
views
Is every language described by a grammar?
I read the following argument showing that not every language is described by a grammar:
For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
4
votes
1
answer
1k
views
What is the computational complexity of "real-life" regular expressions?
Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), ...
- 776
1
vote
0
answers
51
views
Chomsky hierarchy for finite state transducers
In this question in the first answer someone mentions a "special transduction hierarchy". I cannot find anywhere anything about it. Could someone point me to resources on this topic?
- 143
2
votes
1
answer
276
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}, Σ ∪ {#...
5
votes
0
answers
363
views
Where is simply typed lambda calculus on the Chomsky hiererchy?
The functions definable in untyped lambda calculus are the computable functions, for which it is in turn possible to define equivalences to the concepts of Turing machines, recursive enumerability and ...
- 776
0
votes
1
answer
66
views
What kind of Grammar could this be
I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one:
bX -> abY
which Type of ...
- 1
1
vote
0
answers
38
views
CFG to CNF, but stuck on the last few steps
I recently learned about the conversion, but I seem to be stuck.
I need to convert the following CFG to CNF:
$S → XY$
$X → abb|aXb|e$
$Y → c|cY$
There is no S on the right side, so I did not need ...
- 21
-1
votes
1
answer
962
views
Convert CFG to CNF Arithmatic Expression
Convert CFG to CNF
The Grammar
E→E+T
E→T
T→T*F
T→F
F→(E)
F→x
Step 1
Assign variables to terminals
A→ +
B→ *
C→(
D→ )
F→x
...
2
votes
1
answer
303
views
Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?
I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with ...
- 147
4
votes
0
answers
93
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 ...
- 41
1
vote
2
answers
216
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,190
1
vote
1
answer
56
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, ...
- 29.7k
2
votes
1
answer
583
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 ...
- 215
0
votes
1
answer
238
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 \...
- 183
2
votes
2
answers
2k
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
2
answers
538
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 ...
-1
votes
1
answer
835
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 ...
- 251
4
votes
1
answer
463
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 ...
- 95
3
votes
1
answer
2k
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), ...
user102382
0
votes
0
answers
100
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
1
vote
1
answer
112
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:
𝑆 → 𝑎𝑆 | 𝑎𝑅
𝑅 → 𝑏𝑅 | 𝑏𝑇
𝑇 → 𝑐𝑇...
- 13
7
votes
3
answers
2k
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?
- 175