Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
0 votes
1 answer
36 views

Context free grammar $\{0^n 1^m : n,m \geq 0\}$

I just started studying the concept of context-free grammars and I find something very confusing. Watching a video I found someone tackling the problem ${0^n 1^m : n,m\geq 0}$. I thought that the ...
Jellyfish's user avatar
1 vote
1 answer
39 views

Communication complexity of Dyck language

I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
asamsa's user avatar
  • 11
1 vote
0 answers
16 views

Number of DCFG parse tree nodes with respect to input length

I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
Petr Skocik's user avatar
2 votes
2 answers
51 views

Derivation trees to show a given grammar is ambiguous

Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
cpf9231's user avatar
  • 21
0 votes
0 answers
21 views

Lambda Calculus with State

I want to define a typed domain-specific lambda calculus which can simulate the sequence execution like common programming language. I wonder how to give its corresponding BNF, can I use ...
Ziyu Mao's user avatar
1 vote
1 answer
39 views

Is the class of star-free languages just the complement to counter languages within the regular language class?

So I'm kind of confused as I'm not that deep into the algebraic theory of languages. The wikipedia article states: Another way to state Schützenberger's theorem is that star-free languages and ...
Crea Teeth's user avatar
1 vote
0 answers
19 views

Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere

Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
Alex Flint's user avatar
5 votes
1 answer
349 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 ...
Crea Teeth's user avatar
0 votes
1 answer
33 views

An elementary question about grammar

Recently, I am studying grammar in automata. And, I have few information about this subject. I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$. Is it true if I say that $S\to aASA$ ...
user163802's user avatar
0 votes
1 answer
63 views

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
empty-search's user avatar
1 vote
0 answers
31 views

How need help to specify a grammar for arithmetic expressions

I am trying to come up with a grammar for arithmetic expressions with the following order of operations: Parentheses Factorials Exponents Functions / unary plus and minus Juxtaposition (implied ...
Chris_F's user avatar
  • 111
1 vote
1 answer
72 views

Is $L=\{1^n2^n3^m : n\neq m\}$ context free?

Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free? I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
oleshkowitz's user avatar
0 votes
1 answer
50 views

How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?

I have been trying to understand how the language $L = \{a^m b^n c^p d^q \mid m*n=p+q\}$) is context-sensitive? I first encountered this question here. Would be grateful if you could provide some ...
yash's user avatar
  • 1
1 vote
1 answer
77 views

Language of equal numbers of as, bs, cs in any order not context-sensitive?

In his book "Foundations of Computing", professor Allison shows an example of "language of equal numbers of as, bs, and cs, but in any order", formally: $L = \{ w \in \{a,b,c\}^*\ |...
Barney's user avatar
  • 155
-1 votes
1 answer
57 views

Is { a^nb^na^n} a context-sensitive language?

The language $L_1 = \{ a^nb^nc^n \}$ is often given as an example of a context-sensitive language. I am wondering if the language $L_2 = \{ a^nb^na^n \}$ belongs also to the same category?
Barney's user avatar
  • 155
1 vote
0 answers
52 views

Correct way to show example of ambiguous grammar

Facing confusion due to two different texts stating different ways to show examples of ambiguous grammar, though the example exists in the first book. The second book gives a different example, as ...
jiten's user avatar
  • 187
0 votes
1 answer
37 views

The language of chains with twice as many $a$s as $b$s is regular?

I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem: Let $L$ be the language of all words that ...
lafinur's user avatar
  • 181
1 vote
0 answers
31 views

What is a formal grammar equivalent to one-way stack automaton?

As the title says, is there a formal grammar characterization of the class of one-way stack languages?
Hana's user avatar
  • 11
0 votes
0 answers
34 views

Nonterminal Complexity of a context-free grammar

Suppose $G$ is a CFG. $G = (N, T, P, S)$, $Var(G)$ as the cardinality of $N$ $Var(L) $= min {$Var(G)$ | G is a context-free grammar and $L(G) = L$}. I have a problem in understanding a part of proof ...
emma's user avatar
  • 1
0 votes
1 answer
44 views

Doubt in pumping lema for context-free language

I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says: My doubt is: Is there any restriction related to ...
user69507's user avatar
0 votes
0 answers
19 views

Decide if complement of context-free language is also a context-free language

Consider the following grammar $G$: $$S \rightarrow SA \ | \ AS \ | \ aXb \ | \ bXa, \ \ \ X \rightarrow \# \ | \ BXB, \ \ \ A \rightarrow a \ | \ b \ | \ \#, \ \ \ B \rightarrow a \ | \ b$$ Decide if ...
Stanley's user avatar
  • 13
3 votes
1 answer
2k views

Is a machine Turing-complete when it can decide a context-sensitive language?

If a machine can decide a context-sensitive language (like the language of palindromes with a non-linear center) is that fact a proof that the machine is Turing-complete? Can this be used to prove ...
Barney's user avatar
  • 155
0 votes
1 answer
91 views

Is this grammar LL(1) and what is it's parsing table?

Let G be a grammar with non-terminal A, terminal a and these productions: A -> A a It is ...
Ian Rehwinkel's user avatar
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 ...
tafelwasser123's user avatar
0 votes
0 answers
52 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 ...
Zoha Javed's user avatar
0 votes
0 answers
49 views

Right-regular grammar conversion to NFA: production rule with only one variable on right side

I'm trying to convert a right regular grammar to an NFA. I understand that I need to create a state for every variable and add transitions according to the production rules. But what if there is a ...
Grizzly_ed's user avatar
0 votes
0 answers
52 views

How to Remove Left Recursion from this Grammar?

How to remove left recursion in the following Grammar: S→Bb/a B→Bc/Sd/e Im new to this, below is the way I'm doing it: ...
whoAsked's user avatar
0 votes
0 answers
37 views

Devising a grammar for language L = { a^xb^ya^xb^y | x, y >= 0 }

I've been trying to come up with a proper grammar for this sort of language: L = { aˣbʸaˣbʸ | x, y >= 0 } I have failed to find a way to enforce consistent generation of terminals on either part (...
MWR_'s user avatar
  • 1
1 vote
1 answer
33 views

Equivalence of LR(k) and LL(k′) parsers

Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?
Gator's user avatar
  • 11
3 votes
2 answers
2k views

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Here's what Wiki says: And here's what Mike Sipser says in his Introduction to Theory of Computation: The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting ...
Sbeve's user avatar
  • 51
0 votes
0 answers
16 views

step 2 of CFG conversion to Chomsky's normal form

in the step where you have to remove the epsilons, would you need to remove something like this: A -> Bε Or would you simply remove the ones that have epsilon by itself like this: A -> ε
joao pereira's user avatar
-1 votes
1 answer
50 views

The book says 27 terminals but I only see 10. Where are they?

On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the ...
Sbeve's user avatar
  • 51
1 vote
0 answers
44 views

How to develop intuition to come up with Context Free Grammar?

So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam. one of the question is to give context free grammar for these two languages and the ...
SkV's user avatar
  • 11
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 ...
Vincent's user avatar
  • 221
1 vote
1 answer
90 views

How would this grammar be converted to a non-left recursive rule?

With recursive-descent parsing, direct/indirect left recursive rules do not allow top-down parsing. How would this grammar be converted to be non-left recursive? ...
penguin's user avatar
  • 11
1 vote
1 answer
612 views

CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}

The question is the following: Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}. I am able to construct CFG for the set of all palindromes as below: S --> aSa | ...
Elegant Srudent's user avatar
0 votes
0 answers
30 views

First Set for this grammar? Is it Indirect Left-recursive

Given the grammar (Uppercase alphabet is non-terminal, lower-case alphabet is terminal), how to find FIRST set? A -> mB | CD B -> CBn | epsilon C -> pA | epsilon D -> q This is NOT a ...
vfg's user avatar
  • 1
0 votes
2 answers
675 views

Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?

I have been trying to find a a CFG for this language generated. I came to the conclusion that I need three parts When $i \le j$ When $j < 2j < i$ When $j < i < 2j$ I was able to come up ...
Noir Phantomville's user avatar
2 votes
0 answers
136 views

Determining when a substring has a unique parse forest

Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending ...
breandan's user avatar
0 votes
0 answers
59 views

Methods of eliminating ambiguity in CFG

I am looking for all possible ways to find and eliminate ambiguity in CF grammar. Please share your knowledge or opinion (preferably you will indicate the literature so that I can familiarize myself)....
gendalin's user avatar
0 votes
0 answers
53 views

What should be the order of eliminating empty rules and unit rules when converting context free grammar to chomsky normal form?

Let's say that we have a context free grammar G, which is not in chomsky normal form, and we need to convert it to chomsky normal form. The steps involved in the conversion are as follows: Add a new ...
Pratik Hadawale's user avatar
0 votes
1 answer
24 views

Do Left regular grammar describe a language containing the reverse of the strings described by the right regular grammar for another language?

Let's say that we have a regular language $L_1$ that is described by a right regular grammar. Now, assume we have a left regular grammar, can we describe the same language $L_1$ or would the left ...
Pratik Hadawale's user avatar
0 votes
0 answers
22 views

Write grammar that produces a^2^i, for i>0 [duplicate]

How to write grammar for that language: $$ a^{2^i}, i>0 $$. Anyone could help?
Mateusz Woźniak's user avatar
0 votes
1 answer
49 views

In Context free languages, is it okay to substitute multiple same variables at the same time?

Let's say we have the following context free grammar: $S \rightarrow a \\ S \rightarrow SS$ And we do the following two "derivations" for the same string: aaa: $S \rightarrow SS \rightarrow ...
Pratik Hadawale's user avatar
1 vote
1 answer
75 views

How can dfa have more than one sink state? Isn’t it the same state?

I can’t understand How can dfa have more than one sink state? Isn’t it the same state? Maybe there is some examples
Tatiana's user avatar
  • 11
1 vote
0 answers
55 views

What is the formal definition of a combinational logic?

Question Background A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35): The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
Shadow43375's user avatar
0 votes
1 answer
49 views

Convert regex for comma separated value to CFG grammar

I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
user156830's user avatar
2 votes
1 answer
41 views

Duplicate rules in CFG

Suppose I have the following CFG that I would like to bring to CNF S -> TA | bA | Ab | b A -> Aa|a T -> Ab Then I have two options to get rid of the ...
Essam's user avatar
  • 155
0 votes
1 answer
81 views

Simple description of the LR(0) table generator algorithm?

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
Gunther Schadow's user avatar
0 votes
1 answer
119 views

Why Regular Grammar is Left/Right Linear?

From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules) But, my question is why it is mandatory? Can't we ...
Aamod Thakur's user avatar

1
2 3 4 5
26