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 votes
0 answers
31 views

Does my solution follow the FNC for a context-free grammar?

From the starting point we have this grammar: S→AA|AB A→aBa|BbB|BabB B→abB|C C→Cc|Ac The first step is to remove empty (ε) and unitary values. From the example ...
user avatar
2 votes
1 answer
54 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 ...
user avatar
0 votes
1 answer
38 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, ...
user avatar
  • 143
0 votes
0 answers
30 views

Pumping Lemma for CFG $S \to c|aSdSb$

I've given the grammar $G=(\{S\}, \{a,b,c,d\}, \{S\to c \mid aSdSb\}, S)$ and I wanted to make an expression out of it. I tried bringing it into ChomskyNF, but as someone commented below the approach ...
user avatar
0 votes
0 answers
10 views

Is there complexity hierarchy of worlds/environments that are used for simulation or reinforcement learning in AI?

Is there complexity hierarchy of worlds/environments (i.e. state space * action space) that are used for simulation or reinforcement learning in AI? Hierarchy like ...
user avatar
  • 1,351
2 votes
1 answer
35 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?
user avatar
0 votes
1 answer
22 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 <...
user avatar
  • 103
1 vote
1 answer
42 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 ...
user avatar
1 vote
1 answer
132 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 ...
user avatar
0 votes
0 answers
23 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 ∈ ...
user avatar
  • 1
1 vote
1 answer
98 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 ...
user avatar
1 vote
0 answers
25 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 ...
user avatar
  • 23
0 votes
0 answers
27 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: ...
user avatar
0 votes
1 answer
86 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 ...
user avatar
-2 votes
1 answer
72 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$ ...
user avatar
  • 3
0 votes
0 answers
55 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 ...
user avatar
0 votes
1 answer
49 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 ...
user avatar
1 vote
1 answer
31 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 ...
user avatar
0 votes
1 answer
31 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} \...
user avatar
  • 103
0 votes
1 answer
142 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 ...
user avatar
1 vote
0 answers
70 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 ...
user avatar
4 votes
1 answer
732 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), ...
user avatar
  • 691
1 vote
0 answers
28 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?
user avatar
  • 143
2 votes
1 answer
155 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}, Σ ∪ {#...
user avatar
5 votes
0 answers
240 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 ...
user avatar
  • 691
0 votes
1 answer
44 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 ...
user avatar
  • 1
1 vote
0 answers
28 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 ...
user avatar
  • 21
-1 votes
1 answer
244 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 ...
user avatar
2 votes
1 answer
200 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 ...
user avatar
4 votes
0 answers
78 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 ...
user avatar
  • 41
1 vote
2 answers
143 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 ...
user avatar
  • 1,162
1 vote
1 answer
34 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, ...
user avatar
  • 29.1k
2 votes
1 answer
282 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 ...
user avatar
  • 215
0 votes
1 answer
196 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 \...
user avatar
  • 183
1 vote
2 answers
1k 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 ...
user avatar
2 votes
2 answers
514 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 ...
user avatar
-2 votes
1 answer
586 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 ...
user avatar
4 votes
1 answer
335 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 ...
user avatar
3 votes
1 answer
1k 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), ...
user avatar
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? ...
user avatar
1 vote
1 answer
98 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: 𝑆 → 𝑎𝑆 | 𝑎𝑅 𝑅 → 𝑏𝑅 | 𝑏𝑇 𝑇 → 𝑐𝑇...
user avatar
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?
user avatar
  • 175
0 votes
1 answer
112 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?
user avatar
  • 175
1 vote
1 answer
49 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 ...
user avatar
  • 145
0 votes
0 answers
118 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 ...
user avatar
3 votes
2 answers
5k 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$ $\...
user avatar
  • 133
4 votes
2 answers
1k 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 ...
user avatar
  • 381
3 votes
0 answers
156 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 ...
user avatar
  • 367
2 votes
1 answer
1k 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 ...
user avatar
3 votes
1 answer
147 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 ...
user avatar
  • 181