Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
886
questions
0
votes
0answers
17 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
81 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
16 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
411 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
22 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
20 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
29 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
17 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
47 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
25 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
53 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
94 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
37 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
34 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
15 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
58 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
53 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
41 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
63 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
44 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
38 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
35 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
32 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
48 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
58 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, ...
0
votes
0answers
31 views
Is there any grammar parseable by LALR(1) but not LR(1)?
https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, ...
0
votes
1answer
45 views
What are the sufficient conditions for a grammar to be unambiguous?
There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous?
For ...
2
votes
2answers
60 views
Operator name in LL(1) computation
I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(...
0
votes
1answer
17 views
What Do These Symbols Mean in Repetitive Rule Application and How Are They Applied Practically?
Frequently in cs blogs and books I see this notation, =>* and =>+ but I am not sure how it is being applied in a ...
2
votes
2answers
35 views
Why can we (apparently) implement CFG parsers only using (N)DFAs?
I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested.
For parsing those files I ...
1
vote
1answer
15 views
defining a programming language grammar for doing arithmetic
I'm studying programming language design, and I've been taught the grammar below which lets you write basic math expressions.
...
2
votes
1answer
42 views
Finding an unambiguous grammar of a language provided by a CFG
I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman.
In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
1
vote
2answers
88 views
How do I model line comments in a CFG?
Assume we want to define a context free grammar of say a programming language, where on each line everything after the character # until the end of line is considered a comment and should be ignored. ...
1
vote
2answers
31 views
Proving that a specific grammar is ambiguous
How can I prove that the following grammar is ambiguous:
$$ A \to AA\mid B \\ B \to aBb\mid ab $$
I tried finding a string that can be derived in two different ways, but to no avail.
0
votes
1answer
36 views
Crafting a Context Free Grammar
I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem ...
2
votes
3answers
53 views
When are two CFG's different?
If two CFG's differ only in what names they use for their non-terminals, are they different?
For example, are these CFG's different:
$$\begin{align*}
S &\to A \\
A &\to a \end{align*}$$
and
$...
1
vote
1answer
31 views
Check grammar for LL(1)?
If I have to check a Left Recursive grammer for LL(1) then should I check it after removing left recursion?
For example:-
S-> (L)|a
L->L.S|S
If I check after removing Left Recursion then the above ...
1
vote
1answer
34 views
Is substitution done to all occurrences?
In a CFG, we might have :$A \rightarrow AA$ and $A \rightarrow a$ where $a$ is a terminal and $A$ is a variable.
Then if we apply the first rule, and then the second , do we get $aa$ or either $aA$ ...
0
votes
0answers
23 views
How to make the length even for the words whose number of 0s is double its number of 1s? [duplicate]
How do I make a context-free grammar (CFG) for the following language?
$$L = \{w \in \{0, 1\}^* : \#_0(w) = 2\#_1(w)\text{ and } |w|\text{ is even}\}.$$ I have
$$S \to S1S0S0S \mid S0S1S0S \mid ...
1
vote
1answer
128 views
For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free
Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my ...
1
vote
1answer
23 views
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
2
votes
1answer
124 views
CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s}
I know the answer which is:
\begin{align}
S &\rightarrow aS \mid T\\
T &\rightarrow aTbT\ \mid \varepsilon
\end{align}
Now, $bbaaa$ is in the language. But the given CFG cannot generate it. ...
1
vote
2answers
37 views
Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata? [duplicate]
I understand that $\phi$ is a null symbol.
why concatenation of any language L with $\phi$ is $\phi$ rather than L ?
0
votes
1answer
45 views
Context free grammar for L={ ((ab)^n)^m }
I want to write a cfg for the following language:
$ L = {((ab)^n)^m }$ $m,n >= 0$
this language produces (abababababab) where: $n=2, m=3 \\ or \\ n=3, m=2$
I have no idea what to do with it!
0
votes
2answers
59 views
Regular grammar with at most one c
I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure ...
0
votes
0answers
41 views
How to check if a string is accepted by a context-sensitive grammar?
Is there an algorithm to determine membership in context-sensitive grammars?
