Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
0
votes
1answer
212 views

Questions About P, NP, languages [closed]

I'm trying to get a better grasp of computation theory, and have a few questions that I can't seem to find great answers too. Given language L, which is non-recognizable, is L* context free? Is P ...
0
votes
1answer
245 views

Neither Left nor Rightmost Derivations

Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the ...
0
votes
1answer
57 views

Trouble understanding Grammar Rules

I am totaly new to theoretical computer science, so I am sorry if I get the terminology wrong: I was reading the definition of a grammar, what I didn't get was the formal definition of the production ...
0
votes
1answer
56 views

Why doesn't the string match the root?

From Reading 17 of 6.005 — Software Construction: Exercise Reading a Grammar 4: Which strings match the root nonterminal of this grammar? ...
0
votes
1answer
690 views

Is a regular grammar valid if it only contains production rules that have nonterminals in the right operand?

For example: S -> Sa Let's say the alphabet is {a} and that is the ONLY production rule of the grammar. Is that grammar valid regular grammar ? Or valid grammar at all? Can it be a context free ...
0
votes
1answer
147 views

How to write a regular expression to match a string that starts with the same pattern that it ends with

Let's say we want to write a regular expression that matches a string that ends with the same pattern that it begins with. Let's say that we have an alphabet composed of the binary symbols: {0,1} We ...
0
votes
1answer
28 views

Why are these FIRST sets not combined into a single set?

In Sebesta's Concepts of Programming Languages 10th edition on page 189 he explains the concept of $\text{FIRST}$ sets using the following example: $A \rightarrow aB \ | \ bAb \ | \ Bb$ $B \...
0
votes
1answer
111 views

Describing the language formed by a particular grammar

G → G B ⏐ G N ⏐ ε B → ( E ) E → E ( E ) ⏐ ε N → ( L ] L → L E ⏐ L (⏐ ε For this grammar, the prompt asks to describe in the language that this grammar describes and builds. I got to the point ...
0
votes
1answer
2k views

Conditions for LL(1) grammar

One of the conditions for A → α | β to be LL(1) grammar states that If β → ε in one or more steps then α doesn't derive any string beginning with a terminal in FOLLOW(A). Likewise If α → ε in one ...
0
votes
2answers
943 views

Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
0
votes
1answer
212 views

The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
0
votes
1answer
64 views

Right linear grammar special case

According to the definition, the productions of a right linear grammar should have the form of $A\to xB$ or $A\to x$, does $A\to B$ or $A\to xy$ count as productions of a right linear grammar? $A\to B$...
0
votes
1answer
466 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = \{\text{...
0
votes
1answer
125 views

How to choose symbols to replace for this left-most derivation?

I have a context free grammar such as the following: $E→E+T | T$ $T→T×F | F$ $F→(E) | a$ Using the left-most derivation, the following can be derived: $E⇒E+T⇒T+T⇒F+T⇒a+T$ $⇒a+F⇒a+(E)⇒a+(T)$ $⇒...
0
votes
1answer
532 views

Is the given grammar LALR

We are given the following grammar. S-->AS/b A-->SA/a We have to tell if its LALR or not. As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using ...
0
votes
1answer
663 views

Where can I find a reasonable NLP CFG or CSG for English?

I'm looking to do natural language parsing and looking for how the CFG (or CSG) should be defined for English. Surely one'd expect to find one from the internet already, but do you know where? It ...
0
votes
1answer
33 views

Is it “valid” for semantic functions to query outside of the grammar in attribute grammars?

Is it valid (in the sense of formal grammars or formal language theory) to refer to outside of the grammar in attribute grammars? What I mean is that since attribute grammars can contain semantic ...
0
votes
1answer
278 views

Why is this language not context free?

I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not ...
0
votes
1answer
931 views

Context-free language and undecidable

I am working on my midterm sample problems and got stuck on this one. Is this language undecidable? $\qquad L = \{\langle G_1, G_2 \rangle: G_1, G_2 \text{ are CFG and have strings that can be ...
0
votes
1answer
565 views

How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar

Say I have the following grammar: E -> TE' E' -> +TE'| -TE' | λ T -> (E) | id I need to build the finite state machine with the LR(0) items, But I ...
0
votes
1answer
81 views

Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? [duplicate]

Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? I think it is, but I could not find a way to prove it by using push down automaton or any other way.
0
votes
1answer
52 views

Where is the ambiguity in this grammar?

I am trying to understand ambiguous grammar in programming languages. I was given this ruleset and told it was ambiguous. If my understanding is correct, this means that it is possible to create the ...
0
votes
1answer
174 views

Chomsky NF or Greibach NF benefits for LR parser?

Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind: total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating ...
0
votes
1answer
406 views

How can I prove this language is not CFL? [duplicate]

I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m ...
0
votes
1answer
171 views

How to create an LR($k$) grammar for a given language?

How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say: $$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = ...
0
votes
2answers
3k views

What does the language {a, b, c}* exactly mean? How will the automaton for this look like?

What does the language {a, b, c}* exactly mean?
0
votes
1answer
159 views

What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$ [duplicate]

I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers. Also, in general, are there any good methods ...
0
votes
2answers
3k views

Computing FOLLOW sets for LL(1) grammar. Stuck on question

Calculate the FOLLOW sets for all the non terminals: $S \rightarrow bEx \mid Db \mid b \mid F$ $D \rightarrow EDc \mid Y$ $E \rightarrow dED \mid dDY$ $Y \rightarrow ab \mid aDx \...
0
votes
1answer
63 views

Given family of grammars, determine if LR(k)

Parsing family of grammars, determine if LR(k) I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him ...
0
votes
1answer
81 views

Reversing a List from a Context-Free Grammar

Let's say I have a struct_declaration_list of the following type. How do I reverse it? ...
0
votes
1answer
272 views

Help understanding formal language notation

I am reading this text and it is making absolutely no sense to me. It as if it assumed I will understand. Not to mention the writer apparently had a book made and his grammar is poor. Some of the ...
0
votes
1answer
2k views

Computing FOLLOW sets for a LL(1) grammar

I am trying to learn compiler design. But I get confused when I have to deal with computing the follow set specifically for the empty word. Given the grammar: ...
0
votes
1answer
660 views

Is this grammar LL(1)?

Consider following grammar: $$X\to Yc|ZY$$ $$Y\to ab|cX$$ $$Z\to d|\epsilon$$ Can this be converted to LL(1)? Cleary, its not LL(1) because of First/First conflict at first production. Can anyone ...
0
votes
1answer
357 views

Eliminating $\varepsilon$-productions during elimination of left recursion

I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any. I have the grammar $\qquad S \to Aa \mid b$ $\qquad A \to Ac \mid Sd ...
0
votes
1answer
386 views

Determine if two grammars for the same language are ambiguous

I'm reading the book: Formal Syntax and Semantics of Programming Languages. I don't understand this exercise: Consider the following two grammars, each of which generates strings of correctly ...
0
votes
1answer
501 views

Is this grammar ambiguous?

I have the grammar: $\qquad \begin{align} S &\to S = P \mid S \neq P \mid P \\ P &\to NUM \end{align}$ This grammar suffers from left recursion. To eliminate left recursion, I got: $\...
0
votes
1answer
23 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
41 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
70 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
0answers
35 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
38 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). ...
0
votes
0answers
23 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
35 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. ...
0
votes
1answer
41 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 ...
0
votes
0answers
57 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
25 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 ...
0
votes
0answers
29 views

How to determine if a language produced by grammar is recognizable by deterministic pushdown automaton (DPDA)? [duplicate]

I have a following grammar: S -> aSa | bSb | $\lambda$. And I have to figure out whether the language produced by this grammar is recognizable by DPDA. I can't find any theorems about it. Obviously, ...
0
votes
0answers
16 views

Redcue CFG-Eequiv to CFG-SYM [duplicate]

I want to show, that for an CFG G the question wether $L(G)=L(G)^R$ is undecidable. My first try was to reduce from the CFG-Equivalent Problem) $CFG_{EQUIV}\leq CFG_{SYM}$. My first attempt was to ...
0
votes
0answers
24 views

Counting the number of unique syntax trees of a grammar

Lets say we have some arbitrary grammar for which we would like to know how many different syntax trees does it generate. For example the following: S -> A1|1B A -> 10|C B -> C1 | $\varepsilon$ C -...
0
votes
0answers
55 views

context-free language : if yx belongs to cfl then xy is also cfl [duplicate]

I faced a problem. What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language. C is a Context-Free Language. I think we can use the PDA ...

1
15 16
17
18 19
21