Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

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

Explain why a language can be generated by a context free grammar [duplicate]

I have a problem where I am asked to explain why the language that has words made of $a$ and $b$ such that the number of $a$'s is equal to the number of $b$'s, can be generated by a context free ...
2
votes
0answers
15 views

Induction / (machine learning) of Resource Grammars for Grammatical Framework?

Grammatical Framework is based in Abstract Categorial Grammars. It is known that Combinatory Categorial Grammars have grammar induction/learning capabilities see e.g. https://link.springer.com/article/...
0
votes
1answer
132 views

CFG to PDA - no empty transitions

Working for my exam, this question popped up. Given the production rules below, draw a pushdown automaton to recognise the language it generates: S → AB A → BA B → BB B → T T → b ...
3
votes
1answer
150 views

What is the grammar for language $L={a^nb^m : n \neq m-1}$?

What is the grammar for language $L = \{ a^nb^m : n\neq m-1\}$? I only know I have to write grammar for both $ n<m-1 $ and $ n>m-1 $, so this is what I wrote: ...
2
votes
0answers
82 views

How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?

Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure. Let $S$ be the start symbol ...
1
vote
1answer
167 views

L(G) = ∅ is undecidable?

For a grammar $G$, why is the problem of whether $L(G)=\emptyset$ is undecidable? I'm confused as, for recursive languages there exists a Turing machine which will halt every time and give an answer(...
0
votes
1answer
28 views

Which language is produced by this grammar?

I was asked to define the language which is produced by the following grammar: $G = (V, \Sigma, S, P)$ $V = \{S, A, B\}$ $\Sigma = \{a, b, c\}$ \begin{equation} P= \begin{cases} S \...
1
vote
0answers
168 views

Unrestricted grammar is closed under intersection

I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar $G_1$ and $G_2$ that are restricted for example ...
1
vote
0answers
50 views

Examples of context-free grammars whose ambiguity is unknown

Are there any examples of context-free grammars for which we simply do not know whether they are ambiguous? By examples I mean an actual specification for the grammar, not some kind of non-...
0
votes
4answers
309 views

Grammer Class/Production Rules of Programming Languages

I'd read around on the interwebs, and a lot of the text indicated that many programming languages are generated by a context-free grammar, which leads me to 2 questions: Doesn't variable scoping ...
2
votes
0answers
236 views

Context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$ [duplicate]

Find a context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$ where $L \in DCSL \setminus CFL$. I find this task from old exam but there is no solution. I try ...
2
votes
1answer
182 views

Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?

Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous? According to what I studied, every DCFL is guaranteed to have an unambiguous grammar though there are multiple grammars ...
2
votes
1answer
341 views

Is the language given by a context-free grammar always context-free?

Consider the language generated by the following grammar: $S \to aSBb \mid \epsilon$ $B \to aB \mid bB \mid \epsilon$ Is the above language context-free? The above language looks like $\{ w \in (...
1
vote
1answer
515 views

Is the complement of every non Turing recognizable language a Turing recognizable language?

One thing I understand is that the complement of every Turing recognizable(but not decidable) language is non Turing recognizable. What about the complement of non Turing recognizable language? Is ...
1
vote
2answers
82 views

What is the difference between language hierarchy and Grammar hierarchy for LL and LR?

Till now I have believed that a LL language is a language generated by a LL grammar. Same goes for LR. Now I know some of the hierarchies such as $LL(1)\subset LR(1)$. I used to think that the ...
1
vote
1answer
55 views

Figuring out whether LL(1) grammar has an $\varepsilon$-free variant

This question arose out of a concrete problem I had, which was to find an $\varepsilon$-free variant of the following LL(1) grammar $G_0$ that I developed for a Lisp-like language $L$ (I found a ...
2
votes
1answer
558 views

Number of nodes of a parse tree when the Grammar is in CNF?

There happened to be a following question - In any Chomsky Normal Form grammar $G$, how many nodes will all parse trees for terminal strings of length $n>0$ generated by G have? I tried for ...
2
votes
0answers
240 views

Is the complement of $L = \{a^nb^mc^p \, n= m= p\}$ context free language?

Is the complement of $L = \{a^nb^mc^p \ , n= m= p\}$ a context free language. I believe that we can write $L^{'} \ as \ L1 \cup L2$ where $L1=(a^*b^*c^*){'} \ $ $L2={{a^nb^mc^p \ m\ne n \ or \ n\...
1
vote
0answers
311 views

Converting a non-deterministic context free grammar to deterministic

I have the non-deterministic context free grammar $$I \to abcX | abdY$$ $$X \to X d | \epsilon$$ $$Y \to XX |I$$ and i want to convert it into a deterministic. I know that the rules $I \to abcX | abdY$...
3
votes
0answers
120 views

Semantic parsing with Grammatical Framework - is this possible?

So far I have learned about categorial grammars, type logical grammars and formal semantics of natural language, the relevant tools are Cornell Semantic Parsing Framework https://github.com/clic-lab/...
2
votes
1answer
77 views

Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL

I'm trying to prove $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL. Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$. Now I want to show ...
0
votes
0answers
212 views

Deciding whether a context-free grammar's language is empty

Consider the formal problem: Given a context-free grammar $G$, is the language $L(G)$ empty? Can we determine if the problem is recursively enumerable, recursive, in NP, or in P? Can the entire ...
0
votes
1answer
105 views

Prove or disprove: Complement of language $L=\left\{baba^2ba^3b…ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free

Prove or disprove: Complement of language $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free. I'm not quite sure how this is done. I would first try to find out ...
1
vote
0answers
250 views

Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata

I read following here: Unambiguous grammars do not always generate a DCFL. Example: For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-...
0
votes
1answer
138 views

Decidability of whether CFL = RL

Let L1 be a language generated by a CFG. Let L2 be a language generated by a regular grammar. Is L1 = L2 ? Is the above problem decidable or undecidable ? If L1 = L2 then L1 $\cap$ L2' = $\phi$ ...
-4
votes
1answer
407 views

Can any ambiguous context-free grammar be converted into Chomsky normal form? [closed]

Can an ambiguous context-free grammar be converted into Chomsky normal form? I think the answer is yes.
1
vote
1answer
121 views

Prove correctness of this (context-free) grammar

I created a context free grammar for the language which has words where twice as many a than b occur. So as example, the ...
0
votes
0answers
35 views

Find any kind of grammar for the language

Find any kind of grammar for the language L = {w ∈ Σ* | in w there are twice as many a's than b's} and reason its correctness. Where ...
0
votes
1answer
1k views

Construct an equivalent NFA for the given regular grammar

Given is the regular grammar G = ({A,B}, {a,b}, P, A) with the rules P : A → aB, a, ε (where ε is the empty word) B → bA, b ...
3
votes
1answer
52 views

How to explain/understand brackets of applicative functor [[f u1… un]]?

I am reading article about Applicative Abstract Categorial Grammars http://okmij.org/ftp/gengo/applicative-symantics/AACG.pdf and this article uses brackets [[...]] for action on terms inside ...
3
votes
2answers
464 views

How to check for ambiguous grammar if you don't know the string

Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know ...
0
votes
2answers
39 views

Is there a regular grammar for the language $\{ w : |w|_0 = |w|_1 \}$? [duplicate]

I need to prove whether the language $ L = \{w \in \{0,1\}^* \mid |w|_0 = |w|_1 \}$ can be written as a regular grammar. Obviously it can, but how do I prove it?
1
vote
2answers
348 views

Prove grammars with long derivations generate infinite languages

Suppose $G$ is a CNF (Chomsky normal form ) grammar which has $v$ variables. ($|V| = v$) If there is a string that $G$ derivatives in more than $2^v$ steps, prove that $L(G)$ is infinite. Any ...
0
votes
2answers
120 views

Removing epsilon transition from the grammar. What's the difference between accepting languages?

I want to remove the epsilon transition from following grammar: \begin{eqnarray} S & \rightarrow & A | B \\ A & \rightarrow & \epsilon \\ B & \rightarrow & aBa \\ B & \...
3
votes
1answer
2k views

How to eliminate context-free grammar's ambiguity

I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's. I have come up with a couple of possibilties so far. I think they're correct but they're ...
0
votes
1answer
36 views

Grammar types constraint after adding a couple of types (and a statement involving them) to a “typeless” language

Foreword : by "typeless programming language", I naively mean "language in which you don't write statements like type x (=) ... to declare(define) ...
2
votes
1answer
136 views

Is this book's definition of phrase correct?

I am fairly confident that my textbook (Concepts of Programming Languages 11th edition, international edition, Robert Sebesta) has an error in its definition of what a phrase is in the section on ...
1
vote
0answers
26 views

CFG grammar with fixed number of “distinguished” terminals

I would like to know if there is a name for CFG grammars (or grammars in general) in which there is a fixed number of "distingushed" terminals or in which there is a terminal that appears a fixed ...
1
vote
1answer
120 views

Determining Ambiguity of grammar

I read that no LL(1) grammar can be ambiguous. Can we just make a LL(1) predictive parser table for a grammar to determine whether it's ambiguous? If the grammar is not LL(1), can we say that grammar ...
0
votes
1answer
360 views

LL1 parsing algorithm for strings generated by a given grammar

How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar? I have to design a parser for a specific grammar. Let $G$ be the grammar described as: $$S \...
0
votes
1answer
1k views

Is the balanced parentheses language inherently ambiguous? [duplicate]

I have this grammar: $S\rightarrow SS |S \rightarrow(S)|S\rightarrow\epsilon $ Now this grammar generates the set of balanced parentheses. But this grammar is ambiguous. I am trying to find an ...
0
votes
1answer
288 views

Can every CFG be converted into an equivalent CFG of this form?

Question: Show that every CF grammar G = (V,T,S,P) can be converted into an equivalent CFG in which every production is of the form A → xBC or A → ϵ, where x ∈ T U {ϵ} and A,B, and C are variables. ...
2
votes
1answer
272 views

Meaning of $|w| ≡ 2 \mod 3$

I'm new to formal language and automata theory and I was left alone with this exercise. The task is to define a formal grammar for given language. $Σ \in \{a,b\}$ $L = \{ w \in Σ^*\, |\, |w| \...
0
votes
1answer
39 views

Definition of a grammar

I am learning about context free grammars and have been through few texts in a undetailed manner on these topic . I think I should know the exact , rigorous ,technical definition of what exactly a "...
2
votes
2answers
2k views

Is this language context free L=${a^mb^nc^pd^q: m+n=p+q}$?

L={ $a^mb^nc^pd^q: m+n=p+q$ } I cannot find a grammar to prove that it is context free. However I can visualise a PDA which can accept this language. The PDA would push O's for every a and b which it ...
1
vote
2answers
349 views

Context-free grammar for binary words

I am supposed to create CFG for this languague: $L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$ where $|w_b|$ is count of terminals $b$ in $w$. For example: aa - OK, no 'b' abb - wrong, only ...
4
votes
2answers
841 views

Given a language L what can we say about the decidability of whether this language is regular or not?

Can we develop a turing machine which on given a language L as input gives as output whether this language is regular or not?
2
votes
1answer
793 views

How does left-factoring prevent backtracking?

I read that deterministic grammar helps in preventing backtracking. Consider a grammar $$A \rightarrow ab \mid ac \mid ad$$. Here if input is "ad" then the compiler needs to check each of ab, ac .. ...
1
vote
1answer
33 views

Given grammar, a nonterminal, and a string, does there exist a parse tree that uses the nonterminal?

Let $G$ be a CFG, let $A$ be one of its non-terminals, and let $x$ be a string. Define the language = $ \{ \langle G,A,x\rangle|$there exists a derivation of $x$ in which $A$ is used $\}$. Is this ...
1
vote
1answer
178 views

How LL Grammars are subset of DCFL?

I have seen in most of the places written that LL grammars form a subset of DCFL and DCFG. Is there a proof for that?