Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
906
questions
0
votes
1answer
16 views
How to determine valid handle for given bottom up parser?
I came across following question:
Consider the grammar:
$E → E + n\text{ | }E × n\text{ | }n$
For a sentence n + n × n, the handles in the right-sentential form of the reduction are
(...
0
votes
0answers
29 views
How to find a context-free grammar from a difficult language? [duplicate]
Some Languages are trivial to find their respective context-free grammar. Like for example $ L= \{a^nb^n: n \geqslant 0\}$. However some are really difficult to solve. I would like to have some advice ...
0
votes
1answer
19 views
How do we formally regard a function that takes a lookup set as a parameter?
I have a function that takes a set as a parameter. The function $\phi$ maps a general $x \in R$, where $R$ is a commutative ring with $1$, to a $\phi(x) \in \Bbb{N}$ representing the "grammar size" ...
-1
votes
1answer
44 views
Constructing a DFA of strings that are in A but not in B
I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c}
I am not really sure where to even start with this one, ...
0
votes
0answers
77 views
Pushdown Automata - constructing a PDA to recognise a language with at least as many as as bs
I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question)
...
1
vote
1answer
34 views
Context-free grammar how to have unequal number of a's on either side of b
I have been trying to create a CFG for the set
$\{w=a^iba^j \mid i \neq j\}$.
To my understanding, there are essentially 2 scenarios, one where there are more $a$s on the left side of $b$, and one ...
3
votes
1answer
21 views
How to split a context-free language into three sub-languages?
I try to split the language
$$
L = \{a^ib^j \mid i \neq 2j, i \neq 3j\}
$$
into three languages
\begin{align}
L_1 &= \{a^ib^j \mid i < 2j\} \\
L_2 &= \{a^ib^j \mid 2j < i < 3j\} \\
...
1
vote
1answer
32 views
I want to design a context free grammar for the following [closed]
This below language
$$L = \{ w \in \{a, b\}^n : \lvert w\rvert \text{ mod } 3 = 0 \}$$
where $n \geq0$.
2
votes
1answer
79 views
LL(k) language and not LL(k) grammar
I have nonambiguous and not LL(k) grammar which defines some language. How can I prove that I can't build some LL(k) grammar for this language?
Grammar:
S -> a b X c d | a X f
X -> b X c | ε
0
votes
0answers
16 views
Formal definition for strong equivalence of grammars/parse trees
The Wikipedia article on equivalence of formal grammars defines weak and strong equivalence as follows:
In formal language theory, weak equivalence of two grammars means they generate the same set ...
0
votes
1answer
33 views
Are you allowed to use index variables in grammars?
If we say that the grammar for the language $L = \{ww \mid w \in \{a,b\}^*\}$, is:
$\begin{align}
S &\rightarrow A_1A_2S \mid B_1B_2S \mid Z_2\\
A_2A_1 &\rightarrow A_1A_2\\
A_2B_1 &\...
1
vote
0answers
30 views
Ambiguos Grammar detection algorithm
I tried to solve if a grammar is ambiguous or not.
I know that I have to find a word that can be generate by two different leftmost derivations.
Is there any algorithm to find a word that, if the ...
2
votes
1answer
31 views
What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?
In other words, what is the likelihood that a recognizer of a given regular language will accept a
random string of length $n$?
If there is only a single non-terminal $A$, then there are only ...
4
votes
0answers
50 views
Acyclic Manhattan turtle
There is a grammar that describes the walks of a turtle around Manhattan, such that the turtle
always returns home. It is described in the book "Parsing Techniques" by Dick Grune and Ceriel
J.H. ...
0
votes
0answers
24 views
Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion
It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-...
0
votes
0answers
43 views
Is Python's Grammar in a known Category between CFG and CSG?
I have a high level understanding of formal languages and grammars, and
I'm familiar with the four major types of grammars in Chomsky hierarchy.
I was interested in knowing the classification of ...
2
votes
1answer
41 views
Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)
I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer):
Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}...
1
vote
1answer
30 views
Is following grammar has language which is inherently ambiguous?
Grammar is as follow:
$S \rightarrow aaAb | aab | A$
$A \rightarrow aaAb | aAb | \epsilon$
I think that this grammar has equivalent unambiguous grammar as follow.
Let’s first rewrite the grammar ...
4
votes
1answer
35 views
Language containing all unambiguous grammars
Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar.
Considering that deciding whether a ...
0
votes
0answers
53 views
Whether following language is linear or not?
I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$.
Now, I wanted to determine whether this language is linear or not.
So, I came up with this grammar:
$S \rightarrow A\thinspace|\thinspace Sc$
$A \...
0
votes
1answer
16 views
With a grammar, does precedence and associativity change the accepted language?
When parsing, certainly precedence and associativity effect the AST. But, do precedence and associativity alter the set of accepted sentences? In other words, can precedence and associativity be "...
0
votes
1answer
36 views
Create automata from non regular grammar
I have two grammars:
L → ε | aLcLc
L → ε | aLcLc | LL
This two grammars are equals but the first one is regular, so it produces a regular language and a ...
1
vote
2answers
130 views
How do i tell if a grammar is regular or not?
I know that a regular grammar has a definition
$$\begin{align}S &\to aS\\
S &\to \lambda
\end{align}$$
But I dont really know how to apply this information to check whether or not a grammar ...
0
votes
0answers
18 views
Why are CFL not closed under set difference, and complementation? [duplicate]
I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.
3
votes
3answers
437 views
Context-free grammar of the concatenation of a string S and subsequence of reversed S
I have to find a Context-Free grammar that generates the language:
$L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$
The concatenation of two mutually ...
1
vote
1answer
22 views
Calculating LL(1) grammar
I am trying to calculate the First and Follow of the following grammar
S->ABC
A->Aa
A->aB
B->Bb
B-> epsilon
C-> Cc
C-> Epsilon
I have ...
0
votes
0answers
16 views
grammar for the no.of a's one more than no. of b's [duplicate]
write the grammar for the following
L = {w : na (w)= nb (w) + 1}.
*
no. of a’s is one more than no. of b’s
*
2
votes
1answer
28 views
Why $P$ cannot have NULL string in Arden's Theorem?
Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what ...
0
votes
0answers
21 views
Is $LR(k) \subset SLR(k+1)$ for $k=1,2,…$? [duplicate]
I know that:
Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers
Does this logic hold for higher $k$'s? That is, does following fact hold?...
0
votes
0answers
31 views
Does SLR(0), LALR(0) exists?
I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
0
votes
0answers
19 views
Proving correctness of LR parser facts
I have came across following facts while reading some compilers related text. However I did not find them in any standard reference book (mainly dragon book). Are they correct? If yes, how can we ...
1
vote
1answer
56 views
Confusion with first condition of Chomsky Normal Form
I had a very quick question when it comes to CFG (more specifically the attributes of CNF). I've been browsing over some examples and I've come across a few that confuse me. One such example is this:
...
0
votes
1answer
29 views
How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?
I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:
When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
3
votes
1answer
60 views
Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?
In Wikipedia of Kuroda normal form, it says
A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-...
4
votes
3answers
96 views
How to give a context-sensitive grammar for a^nba^nba^nb?
I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.
1
vote
1answer
40 views
Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it?
E -> E * B .
E -> E + B .
E -> B .
B -> 0 .
B -> 1 .
I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar ...
0
votes
1answer
48 views
Is there a LL(K) Grammar which is not LALR(K) Grammar?
It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And ...
0
votes
0answers
16 views
FOLLOW of LL(1) grammar [duplicate]
Please consider following grammar:
E -> P : P
P -> X R
R -> . P | ε
X -> num Y
Y -> num Y | ε
I am searching FIRST/FOLLOW.
First:
...
1
vote
1answer
62 views
Connection between non determinism and LL(1) conflicts
I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it.
As per my understanding non deterministic context free grammar is a context free grammar ...
3
votes
1answer
56 views
Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?
Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language?
It certainly isn't regular, but is it context free?
I'm having trouble creating ...
1
vote
1answer
50 views
context-free grammar for comma-separated list with comments
I'm trying to write a context-free grammar for a comma-separated list of statements with comments. It is trivial if the comma appears at the end of a statement. It is trivial if the comment is ...
0
votes
0answers
42 views
What is the best algorithm known to learn the regular expression from a set of positive examples?
I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I ...
2
votes
1answer
66 views
In what sense a type of parser is less power than the other?
I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers.
I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the ...
0
votes
0answers
25 views
finding grammar for language with 2^n same characters [duplicate]
Disclaimer: This is a homework question.
Given the language $L=\{a^{2^n}| n\in\mathbb{N}\}$:
1. find a corresponding grammar
2. give a derivation of $a^{2^3}$
3. In which Chomsky hierarchy is this ...
0
votes
1answer
50 views
Construct a grammar for the language
How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must ...
1
vote
1answer
48 views
Proving that the set of grammars generating L or L complement is undecidable
Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
0
votes
1answer
38 views
The problem of equivalence of a CFG and a RG? [duplicate]
Given a context-free grammar and a regular grammar, check whether they are equivalent.
It's a fact that it's undecidable, but how could I prove it?
I want to clarify that my question is not about ...
1
vote
1answer
33 views
Undecidability of checking whether all words can be generated from a context-free grammar?
I know it's undecidable, but how to prove it?
Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate ...
0
votes
0answers
50 views
Creating a grammar for a a language for instructions, with repititions
I have a language that consists of instructions for movement on a 2D-plane. You start at coordinate [0,0]
The instructions
DOWN 1 UP 10 LEFT 5 RIGHT 1
means you ...
0
votes
2answers
138 views
Convert this language to Context Free Grammar
I'm having trouble understanding how to convert this language to context free grammar.
$\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$
Part im getting stuck on is how to deal with a and c, ...
