Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
955
questions
1
vote
1answer
38 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
55 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
552 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
36 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
59 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
65 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
18 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
61 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
19 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
133 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
137 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
49 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
56 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
55 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
80 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
35 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
32 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
287 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
25 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
275 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
47 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
48 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
62 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
82 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
69 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
52 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
156 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
56 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
51 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
61 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 ...
2
votes
1answer
47 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
67 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
42 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
111 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
66 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
61 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
156 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
190 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
395 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 ...
4
votes
1answer
63 views
Is there a recommended process for designing CSGs (other than intuition)?
I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the ...
0
votes
0answers
49 views
Difference between grammar productions and derivations
My understanding is that a production is a 'rule' of a grammar which defines how a symbol sequence can be rewritten into another symbol sequence.
A derivation on the other hand is the process of ...
-2
votes
1answer
55 views
Provide “regular” grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$} [duplicate]
I'm trying to understand the approach to constructing an grammar which accepts the language
${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$ }
Thanks.
0
votes
0answers
43 views
What is “Phrase structure grammar”?
I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar:
Type-0 grammars generate recursively enumerable languages. The
...
0
votes
1answer
149 views
Does left factoring CFG make it unambiguous?
I came across following problem:
If the CFG is left factored then it must be Unambiguous and Not left Recursive.
TRUE/FALSE?
I have many thoughts about this. But I feel they are somewhat ...
0
votes
1answer
126 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 \...
1
vote
1answer
42 views
Is this context-free grammar correct for this regular expression?
I have created a context-free grammar
$$
\begin{align*}
&S \to S_1 \mid S_2 \\
&S_1 \to aS_3bS_4 \mid \epsilon \\
&S_2 \to bS_4 \\
&S_3 \to aS_3 \mid \epsilon \\
&S_4 \to aS_4 \...
1
vote
3answers
110 views
Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2
Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$
whereas $|w|_a$ is the number $a$'s in ...
0
votes
1answer
26 views
How to generate a grammer from this language? [duplicate]
I'm trying to generate a grammar from this language:
L={a^i b^j c^k d^l : i+j=k+l}
to be clear its a in the power of i and b in the power of j... and so on, so ...
1
vote
1answer
112 views
Is there any relationship between grammar being ambiguous and the language itself?
According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language ...
0
votes
1answer
80 views
Ambiguous grammar to equivalent unambiguous grammar
I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.
Given the ambiguous CFG :
$S \to A\mid B$
$A \to aAb\mid ab$
$B \to abB\mid \epsilon$
My ...
