Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
1
vote
1answer
19 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
0
votes
0answers
12 views

Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
1
vote
1answer
20 views

How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?

This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\...
0
votes
0answers
18 views

CFG for the language x^n y^m, where n ≥ 1, m ≥ 1, and n ≠ m [duplicate]

Can anyone help me construct a CFG for this? It really has me stuck for some reason.
-3
votes
0answers
23 views

Is it context-free, regular, both or neither?

Anyone have advice on how to proceed with this? Thanks a lot!
0
votes
1answer
11 views

Are these production rules for a formal grammar?

I have a question on if production rules of a formal grammar are being specified correctly. Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states ...
-1
votes
1answer
35 views

Transform grammar to Chomsky Normal Form

Question: S → abSab | baSba | TT T → aTa| bTb | ε My answer: Eliminate ε rules: S-> abSab | baSba | TT | T T-> aTa | bTb | aa | bb Correct answer: S → abSab | baSba | TT | abab | baba | T T → ...
0
votes
2answers
26 views

How to tell if a grammar is LALR(1) formally?

There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations ...
0
votes
2answers
57 views

How do Context Sensitive Grammar systems work?

The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result ...
1
vote
1answer
107 views

Linear Grammar in less than cubic time

I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types. Is there an algorithm to determine whether $s \in L(G)$ ...
2
votes
1answer
36 views

Is “A -> aAA” convertible to regular grammar?

I have a simple grammar as below and wonder if it is convertible to regular grammar? If yes, what is the conversion sequence? If no, how can we prove it? ...
1
vote
1answer
20 views

How to find the language of a CFG from Production rules

I'm having problems in finding language of the CFG from given production rules. For example if the production rules are \begin{align} &S \to AS \mid \epsilon \\ &A \to aa \mid ab \mid ba \mid ...
-1
votes
0answers
19 views

How to find s->ss|(s)|s(s)s|Epsilon is ambiguous or not?

I have some problem with solving the above question.How can i solve that problem by using left most derivation.
6
votes
1answer
348 views

What are the closure properties of LL(k) languages?

Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by ...
0
votes
1answer
24 views

left/right derivations of grammars and parse trees

I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct. $S-> NP$ $V$ $NP$ $NP -&...
0
votes
0answers
27 views

Converting a regular expression to a grammar and regular grammar

I am working on a pretty small lab for my university course and I'm having trouble converting a given regex into a set of regular definitions, then into a grammar and finally a regular grammar. I have ...
0
votes
0answers
13 views

What's the context-free grammar for { w | 2*(number of a's in w) != 3*(number of b's in w) +2 }? [duplicate]

So I have this language: $$ A= \{ w \in \{a,b\}^* \mid 2*\#_a(w) \ne 3*\#b(w) + 2\} $$ I know it's context free, I know how to make a PDA for it, I just can't, for the life of me, figure out how to ...
0
votes
0answers
16 views

Show {𝑎^i𝑏^j𝑐^k, i!=j!=k} is context free or not, how can we prove it? [duplicate]

I stuck on this question for a long time and cannot figure out how to prove it?
0
votes
0answers
23 views

Show {𝑎^i𝑏^j𝑐^k, 𝑖!= j and 𝑗 != 𝑘} is a context-sensitive language, what is the grammar? It is context free or nor?

I've been pondering this question for a long time, that 𝑎^i𝑏^j𝑐^k, 𝑖!=j and 𝑗 != 𝑘 is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such ...
4
votes
1answer
616 views

Is every unambiguous grammar regular?

While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I ...
0
votes
1answer
45 views

a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive

I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such a ...
0
votes
0answers
18 views

Do the SLR and LALR parsers of a same CF grammar have the same shift actions?

In theory, given that: The LALR parser can be constructed by merging LR(1) states with the same core; If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$; ...
0
votes
0answers
23 views

ANTLR G4 grammer for math expression

I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below. ...
0
votes
0answers
29 views

Constant single match regex

I am looking for the name (definition?) of X in: A regular expression is X iff it has exactly one possible match. Examples: <empty regex>, abc, ...
0
votes
0answers
21 views

Use of graph grammars/rewriting systems in compilers?

A(n imperative) program - in a higher-level language and more importantly in assembly language or intermediate representations like LLVM - can be formalized as a directed "port graph", in ...
1
vote
0answers
46 views

How to write “∀x.F(x)” for “F(x)=λx.Φ(x)” in one expression (sequel from question about “∀(λφ. (φ x m→ φ y))”?

This question is sequel from How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"? which further explains the notation and context. So - I have anonymous Boolean-valued ...
0
votes
0answers
39 views

Is this grammar in Backus–Naur form?

I'm a newbie and a paper I'm reading specifies the following grammar: ...
0
votes
1answer
60 views

Converting PDA to CFG

I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
1
vote
0answers
53 views

Is every language described by a grammar?

I read the following argument showing that not every language is described by a grammar: For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
0
votes
1answer
25 views

If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?

I was studying automata theory and formal languages and came across this question: If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ? I've searched the theory but I am missing ...
0
votes
1answer
43 views

Is there any official terminology about something like double quotes “” grammar?

In many programming language string is a token. For example: ...
0
votes
1answer
100 views

Removing left factoring from Context-Free Grammar

I know that, removing left factoring is a simple task. And i understand following procedure: $S→aA | aB$ Becomes: $S→aS'$ $S'→A|B$ Yet I'm running into problems with this particular grammar: $S→AD|...
0
votes
1answer
79 views

Enumerator for Word and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
0
votes
1answer
49 views

Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$

Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and ...
-1
votes
1answer
78 views

How to design a formal grammar to convert EBNF description to a list of CFG production rules

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm. Can CFG production rules is generated from an EBNF description by a rewrite ...
0
votes
0answers
37 views

What is a make sense (meaningful) example of language that an unrestricted grammar could generate?

I have learned that: Unrestricted grammar is used to define (or describe) a formal language. Unrestricted grammar is used to define recursively enumerable set [https://en.wikipedia.org/wiki/...
0
votes
0answers
39 views

Turning grammar to LL(1)

I have difficulty / doubt in transforming a grammar into LL (1), I tried remove left recursion but grammar still not LL(1). ...
1
vote
1answer
48 views

Help with context free grammar excercise

So, I have an exercise in which I have to write a context free grammar for this language: $$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$ meaning every string with any ...
0
votes
0answers
25 views

Is there any good method to find if a grammar is optimal for a problem?

I've been thinking about grammatical evolution problems and how the grammar influences the algorithm performance. It came to my mind the huge impact that the grammar that you're using has in the time ...
0
votes
2answers
37 views

removing indirect left recursion

I want to remove indirect left recursion from these rules: S-->TU, T-->US|b, U-->ST|a I don't know if I can implement the algorithm correctly. ...
3
votes
0answers
44 views

Are there context free grammars for all restricted Dyck paths?

A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...
0
votes
1answer
54 views

How to remove null production from context free grammar?

How to remove null production and simply the grammar? $$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$ Can the simplification result in this CFG? $$ S \to a \mid aBa \\ A \to ...
-1
votes
1answer
21 views

How to simplify context free grammar?

How to simplify this context-free grammar into a similar one with no unit productions and no useless symbols? $$ S \to ABA \\ A \to aAA \mid aBC \mid bB \\ B \to A \mid bB \mid Cb \\ C \to CC \mid cC ...
0
votes
0answers
58 views

What does it take to create a new programming language and its toolchain?

I am super novice to this topic, so my apologies if my question looks completely nonsense to you all! Imagine you want to create a new programing language that transpiles to a more common high/low-...
0
votes
0answers
26 views

Upper bound on size of derivation in CFG

Suppose $G$ is a $CFG$ with $m$ variables, in which the right-hand side of all production rules has length at most $\ell$. Show that if $A\Rightarrow^*_G\varepsilon$, then there is a derivation of no ...
1
vote
1answer
434 views

What are the modern alternatives to Backus–Naur form and what are their advantages?

I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of ...
1
vote
1answer
202 views

What are the known ambiguities in C language grammar?

I have found this reference for the C syntax Backus-Naur Form (BNF). I was wondering if there are any other ambiguities in this grammar other than the infamous "dangling else"? Also how we ...
0
votes
1answer
18 views

Predicitve Parser LL(1) condition

Lets say we use the predictive parser LL(1). Why is it necessary that $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$, for all $\alpha, \beta$ right side of alternative productions i.e., productions ...
2
votes
1answer
37 views

Is s-grammar powerful enough to generate all possible DCFL?

In s-grammar all productions are in form of A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V* "... and any pair (A, a) occurs at most once in P." [P. Linz, 6th ed. , p. 144] s-...
1
vote
1answer
23 views

Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages)

I want to stress that i am not looking for a proof of this question, but rather if someone(that is familiar with the proof and it's context) can explain to me what the symbol 'e' means in the context. ...

1
2 3 4 5
22