Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
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
156 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
32 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
47 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
61 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
39 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
17 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
57 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
100 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
33 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
43 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
39 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
29 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
155 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
24 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
152 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
41 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
60 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
62 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
46 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
51 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
140 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
55 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
43 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
59 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
35 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
59 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
40 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
60 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
65 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
115 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
161 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
209 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
60 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
31 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
54 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
35 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
82 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
104 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
40 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
103 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
25 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 ...