Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1
vote
1answer
12 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
39 views

Is this a regular grammar? What rules make it regular? [on hold]

$\Sigma = \{a,b\}$ $G=\{\{A,B\}, \Sigma, \{A \to BB, B \to aB\mid bB\mid \epsilon\}, A\}$ Is this a regular grammar? Can you justify why is or is not rule by rule?
2
votes
1answer
29 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
69 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
29 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
31 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
47 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
22 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
31 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
21 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
91 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
22 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
61 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
33 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 ?
-1
votes
0answers
30 views

Find a context-free grammar for L={(a^n b^m)^z d^z} [duplicate]

need a CFG for the following language: $L={(a^n b^m)^z d^z}$ $m=2n, \ \ \ n,z \\$≥0 Any ideas?...
0
votes
1answer
38 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
55 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
28 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
31 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
45 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
62 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
50 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
38 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
56 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
31 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
43 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
35 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
28 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
53 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
54 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
80 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
118 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
38 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
54 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
17 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
48 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
22 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
42 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
57 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
39 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
81 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
24 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
43 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
54 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 ...
1
vote
2answers
44 views

What's the right way to think about a CFG symbol with an infinite null derivation?

I'm curious about the right way to characterize symbol $A$ in a CFG like this one: $$ \begin{align*} A &\to A B\\ A &\to x\\ B &\to y\\ B &\to \varepsilon \end{align*} $$ $B$ is ...
2
votes
1answer
18 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
-1
votes
2answers
91 views

How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]

i am trying to find a cfg for this cfl L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$ is there a way to count the number of 0's or 1's in the string?
1
vote
2answers
83 views

Buchi automata in formal software verification

As I am studying the application of Buchi automata in formal software verification, I am interested in the computational complexity (or links to papers) for the algorithms used to solve the problem in ...
1
vote
2answers
81 views

Is every subset of a RE language also RE, in general?

I'm trying to understand the question in my title in an intuitive way: If I have an RE language A, then some TM, say TM(A) accepts on it. If I take a subset of A, say A2, then all elements of A2 will ...
2
votes
2answers
392 views

Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...