Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
0
votes
1answer
21 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
50 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
49 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
38 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
56 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
39 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
33 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
30 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
45 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
45 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
28 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
39 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
59 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
30 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
14 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
41 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
79 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
34 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
50 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
27 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
110 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
110 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
35 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
44 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
58 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
35 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?
1
vote
2answers
36 views
Program to check whether a string is accepted by an unrestricted grammar
How can I write a program to find out whether a given string is generated using a type 0 grammar (unrestricted grammar)?
3
votes
1answer
50 views
Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m
I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated.
The professor hasn't given the correction.
I have seen similar questions but the condition ...
0
votes
0answers
106 views
The rightmost derivation is possible with the same rule of leftmost derivation
Can someone please help me in understanding the statement. What does it exactly mean?
What I think it means is that:
the derivation produces by the leftmost derivation is also possible with rightmost ...
0
votes
0answers
53 views
Grammar for context free language
I want to give a grammar for the following language:
$$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$
where $x ^ r$ denotes the backward written ...
0
votes
1answer
42 views
Is this language L context-free?
The language
$$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$
where $x ^ r$ denotes the backward written word x, is context-free.
Can someone ...
1
vote
1answer
57 views
Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side?
Is the following true or false? Why?
Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are ...
1
vote
1answer
34 views
Is this a proper LL(1) Grammar?
Please take this question with a grain of salt. I'm trying to write a very simple layout engine and wanted to formally create a grammar to parse the input. I stayed up all night researching LL(k) ...
1
vote
1answer
50 views
Can there still be infinite recursion if I remove all left recursion?
I have to transform the following grammar into a non left recursive grammar:
S → aSb | bAS
A → AaA | bAA | AAa | bAb
This is what I came up with:
A → bAAA’| bAbA’
A’ → aAA’| AaA’| ε
S → aSb | ...
1
vote
1answer
38 views
Constructing CFG
How to generate CFG for this language?
$ L = \{ w \mid w \in \{ (, [, ], ) \}^* \text{ s.t. } $
In any prefix of $w$, no. of ( is more than no. of ), and
no. of [ is more than no. of ].
$\}$
Thus,...
1
vote
1answer
42 views
Converting CFG from GNF to CNF
I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is ...
-1
votes
1answer
64 views
How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
I don't have any idea. Can someone help me.
0
votes
1answer
56 views
Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free
$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$
In my opinion complement of the L language is
$L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$
I choose to ...
1
vote
2answers
89 views
Is the language of words that contain a square regular or context-free? [duplicate]
$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$
I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
3
votes
2answers
144 views
How to prove the equivalence of two CFG for balanced parentheses?
Given two CFGs for balanced parentheses.
$S \rightarrow SS \mid (S) \mid \epsilon$
$S \rightarrow S(S)S \mid \epsilon$
How do I show that they are equivalent?
I have been able to show $ L(2) \...
1
vote
1answer
65 views
Prefix/suffix property of language containing only empty word
Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?
The definition says that language has prefix/suffix property requires that there is no code word in the ...
