Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
1
vote
2answers
312 views

There exists an algorithm to find grammar of complement of a function?

I'm wondering if there exists an algorithm to solve the following problem: Given a grammar $S$ of a context-free language $\mathcal{L}$, find a grammar $S'$ such as $L(S) = L(S')^c $. I note ...
0
votes
0answers
36 views

How to include both precedence and associativity in following grammar?

For the following grammar, how can I include both precedence and associativity of operators: S -> S|S S -> S.S S -> S* S -> (S) S -> a|b Note: In the first rule ...
3
votes
2answers
378 views

If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?

I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack. But, a link of Show that { ...
0
votes
2answers
70 views

Is this correct grammar definition of Backus-Naur form?

I've been given a grammar definition of "Simple C language" in Backus-Naur to write a compiler for a class assignment. I've been trying to implement the parser for some time now and I just can't move ...
0
votes
1answer
268 views

What does {a,b}* for DFA's mean?

For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has? For example a DFA that accepts $\{w \in \{a,...
1
vote
1answer
68 views

Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

I'm trying to proof that the following language is not regular using pumping lemma. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$ I started by stating that: $|w\bar{w}| =...
1
vote
2answers
156 views

Context-free grammar for ${a^n b^n a^n}$

I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can ...
0
votes
1answer
55 views

Is this grammar LL(1) grammar?

Is this grammar LL(1)? Would it be a problem that S can be both E/S and E? S -> E / S S -> E E -> letter E -> ‘ S ’ Can it derive ‘a / e / ‘g / s’ ’...
0
votes
0answers
58 views

I´m having problems with this Context Free Grammar

I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series ...
0
votes
1answer
43 views

Textbook for understanding formal grammars

I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably ...
0
votes
2answers
463 views

Why LL(1) grammar generate all regular languages?

I came across following: Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages. I tried to get that. Definition: Right linear ...
0
votes
1answer
36 views

Adding constraints in grammar for Grammatical Evolution

I'm trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p ...
0
votes
1answer
25 views

Ambiguous Grammar demostration exercise

Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows: $$S \rightarrow aT | bR$$ $$R \rightarrow a | aS | bRR$...
1
vote
1answer
123 views

How to write grammar production rules to describe recursive structures?

I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $A$ made of elements of type $A$ or $B$. Writing the grammar, I build this: $(S \...
2
votes
1answer
35 views

How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?

In the context of languages (not grammars), I know following: $LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$ $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)...
2
votes
2answers
100 views

Grammar with fewest variables

I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints. ...
1
vote
1answer
46 views

Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ I've tried the following: $G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \...
0
votes
1answer
522 views

Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
1
vote
0answers
43 views

Deciding whether CFG generates the empty word

Give an algorithm to decide the following problem: given a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it generate the empty word? How can I make sure my algorithm is ...
0
votes
0answers
588 views

Grammar for language L on {a, b} where L = {w|na(w)mod 3 = 0} [duplicate]

I am able to form the regular expression but I am not confident with the grammar. I have tried the following: S-->aaaS|bS|b|lambda Regular expression is given by: ...
2
votes
1answer
796 views

How to simplify context free grammars?

How to simplify this context-free grammar? $$ S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b $$ Can the simplification result in this CFG? $$ S \...
2
votes
1answer
109 views

Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{...
3
votes
2answers
275 views

Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a

I have created the following solution but its left recursive: S--> a|bSc|cSb|Sbc Also it is not accepting: "ab" or "cba" or "abb" or abc. Somebody please guide me. Zulfi.
1
vote
2answers
59 views

Useless production

Kindly consider the following productions. How can I identify a useless production? S->aS|A|C A->a B->aa C->aCb Somebody please guide me. Zulfi.
0
votes
1answer
516 views

How to convert the left recursive grammar into right recursive grammar

I have a grammar: $A\rightarrow Aa|bB|c$ The above is the left recursive grammar. I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to ...
2
votes
0answers
191 views

Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules

I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
1
vote
1answer
25 views

What does the term “top-most” mean in the context of formal grammars?

I was learning about disambiguating grammars. In particular I was learning about enforcing right associativity on the sum language here: $$ \mathit{Sum} ::= 0 \mid 1 \mid \mathit{Sum} + \mathit{Sum} \...
0
votes
0answers
59 views

Converting from cfg to cnf (Chomsky normal form)

I am trying to convert this grammar from context free grammar with kleene star productions into the Chomsky normal form equivalent. I am having a hard time trying to understand how to do this, I need ...
1
vote
1answer
87 views

Making a CFG for a^i b^j c^k such that i+k < 3j

I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG. I have thought about solving this for a long time but but this still hasn't gotten me ...
-2
votes
2answers
134 views

Why Rice theorem work for decidability?

Rice's theorem states: Every nontrivial property of recursively enumerable language is undecidable. I came across following problems, which Ullman's books say both are undecidable: Turing ...
1
vote
1answer
63 views

What is the computational power of Parsing Expression Grammars?

Parsing Expression Grammars were introduced by Bryan Ford in Parsing Expression Grammars: A Recognition Based Syntactic Foundation.. Wikipedia says that it is an open problem to provide a Context Free ...
1
vote
0answers
60 views

Prove that grammar $S \to aSc | \epsilon | bBc$ ,$B \to bBc | \epsilon$ generates language $\{a^ib^jc^{i+j} | i,j \ge 0 \}$

Prove that grammar $G$ with productions: $S \to aSc|\epsilon | bBc$ $B\to bBc | \epsilon$ Generates language $ L = \{a^ib^jc^{(i+j)}$ | $i,j \ge 0 \} $ Step 1. Prove $L(G) \subseteq L$ . We are ...
1
vote
1answer
20 views

Variable derives itself

In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim. Consider the grammar: $$ \begin{align*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \...
0
votes
1answer
716 views

Does every regular language have a linear grammar?

Some definitions and facts (from Wikipedia): A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. the left-linear or left ...
0
votes
0answers
43 views

Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
6
votes
1answer
292 views

Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $S \rightarrow aSbS\;|\;\epsilon$ $S \rightarrow ...
2
votes
2answers
186 views

Grammar and Real-numbers

I am curious about following question. I've read other threads but the problem is slightly different: Is the set of real numbers a language? So my question is: If I have a grammar, as defined in ...
2
votes
1answer
41 views

How do I call a system like a grammar, but where a rule has to be applied to all matches at once?

For example, given rules $\{ a \to x, a \to y \}$ and input $aa$ , I am usually allowed to derive strings $\{ xx, xy, yx, yy \}$. I would like to restrict this to only performing "consistent" rewrites,...
2
votes
1answer
257 views

Context-free grammar for $\{a^x b^y : x \neq y\}$

I am trying to create a context free grammar in Extended Backus–Naur form, which starts with a non-empty sequence of a's and is followed by a non-empty sequence of <...
5
votes
3answers
142 views

How do I calculate the Nth result of a context-free grammar?

Given a context-free grammar and a maximum depth, how do I directly compute the Nth sentence without calculating or caching intermediary sentences? Take as an example the following grammar: (from ...
2
votes
1answer
139 views

Are Context-Free Grammars with only one Production Rule always Unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $\require{cancel} \cancel{S \rightarrow aSSb\;|\;\...
0
votes
1answer
25 views

Confused about substitution in grammar in certain cases

To illustrate my confusion let's say I'm given this unambiguous grammar in BNF: ...
1
vote
1answer
42 views

How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?

I don't get how to intuitively come up with an example for an ambiguous grammar. Let's take as an example this grammar: ...
1
vote
1answer
187 views

Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form

The grammar have the following producitons, \begin{align} S&\rightarrow aTbS \mid\epsilon\\ T&\rightarrow aTb\mid\epsilon \end{align} Already turned this homework in, but I need to convert ...
2
votes
1answer
52 views

An example of a context-sensitive grammar for a given language

Consider this language: $L = \{a^nb^ma^nb^m \mid n,m \ge 1\}$. Can we give for this language a context-sensitive grammar?
1
vote
1answer
31 views

Does BNF terminate on a first match?

I know that the grammar <expr> = <expr> + <expr> | <num> <num> = 0|1 is ambiguous because it cannot decide between (1+1)+1 or 1+(1+...
0
votes
1answer
378 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
0answers
143 views

How to find a context-free grammar from a difficult language? [duplicate]

Some Languages are trivial to find their respective context-free grammar. Like for example $ L= \{a^nb^n: n \geqslant 0\}$. However some are really difficult to solve. I would like to have some advice ...
0
votes
1answer
20 views

How do we formally regard a function that takes a lookup set as a parameter?

I have a function that takes a set as a parameter. The function $\phi$ maps a general $x \in R$, where $R$ is a commutative ring with $1$, to a $\phi(x) \in \Bbb{N}$ representing the "grammar size" ...
-1
votes
1answer
49 views

Constructing a DFA of strings that are in A but not in B

I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c} I am not really sure where to even start with this one, ...

1 2 3
4
5
22