Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
0
votes
1answer
36 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 ...
0
votes
0answers
352 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
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
2answers
46 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?
0
votes
1answer
443 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
0answers
728 views

Proof of every regular language has a LL(1) grammar

I tried some examples and found that LL(1) grammar always exist. I tried searching for formal proof but didn't find any. Can someone give a formal proof for the above statement?
0
votes
0answers
47 views

Is this language equivalent to this grammar?

The book that I'm reading says it is equivalent But what about the aa string ? i produce it this way : $$ S\Rightarrow S_1B\Rightarrow aS_1bB\Rightarrow aaB\Rightarrow aa $$ But that language doesn'...
0
votes
1answer
219 views

Find the Context Free Grammar

Let $\Sigma = \{a, b\}$. For each of the following languages, find a grammar that generates it. (a) $L_1 = \{a^n b^m : n\geq 0, m>n\}$ (b) $L_1^3$ (C) $L_1^*$ I know the grammar for the ...
0
votes
2answers
1k views

Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$

I want to build a context sensitive grammar for the language $\{a^{2^n}\mid n\geq 0\}$. I think it should be something like this \begin{align*} S &\to aA \mid a\\ aA&\to aaaA \mid aa \end{...
0
votes
0answers
28 views

Generate a Grammar from a language(Non-CFL) [duplicate]

I tried to solve this question, We have this Language, L(g)={AA|A={0+1}*} The output(Productions) must be similar as these = {(11 11), (0 0), (1101 1101), etc..} The left side equal to right side.. ...
0
votes
0answers
52 views

Is this grammar L4 ambiguous?

S-> AAB|ABA|BAA|epsilon A->aS B->bS this is a grammar of the language L4 = {w ∈ Σ*: #a(w) = 2#b(w)} over Σ = {a, b} Does the following examples shows that the L4 is ambiguous? S->AAB->aSAB->aAB-...
0
votes
0answers
23 views

Constructing CFG from instructions where you have an OR [duplicate]

My question is: What tips or ideas do you have when you're gonna construct a CFG out of these instructions? If we only had 0 < i <= k, it'd be more straight forward if you ask me, but when we ...
0
votes
0answers
54 views

Does $LL(K)$ grammar has one to one correspondence with $DCFL$? [duplicate]

Does $LL(K)$ grammar has one to one correspondence with $DCFL$ ? If I am understanding right, then the given statement says that $2$ distinct $LL(k)$ have one to one mapping, i.e they should not ...
0
votes
0answers
2k views

How to construct regular grammar (right linear and left linear both) from regular expression?

I am interested in some kind of algorithm to achieve this. Basically here is the regular expression aa*(ab+ a)* and I want to construct a regular grammar for this....
0
votes
0answers
156 views

Grammar quine - Formal grammar self-definition

Is it possible to derive a grammar with iself? Or more precisely, is it possible to conceive a grammar which language contains that grammar? For example, the Wikipedia article about BNF claims to ...
0
votes
0answers
1k views

Difference between LR parsing and Shift-Reduce parsing?

I'm learning natural language processing and I can't understand the difference between Shift-Reduce parser and LR parser. As I've understood from Wikipedia, shift-reduce is just a name of a class of ...
0
votes
0answers
829 views

Can any left recursive grammar be converted into equivalent right recursive grammar and vice versa

I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows: Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB ...
0
votes
0answers
86 views

Showing $L=\{a^ib^jc^k: i,j,k \text{ not all equal}\}$ is a CFL a lemma [duplicate]

In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's ...
0
votes
0answers
113 views

Is grammar S→aaab | aab in LL(2) but not SLL(2)?

I'm trying to figure out how to create grammars which are LL(k) and not SLL(i). Is this grammar LL(2) and not SLL(2)? $S \to aaab \mid aab$ Where S is a starting symbol. I think it is not SLL: ...
0
votes
0answers
53 views

Stuck on Converting to Chomsky Normal Form,

I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form. Here is the language: S → AA|SBBa|b A → ...
0
votes
0answers
917 views

Show that any LL(k) grammar is unambiguous

I am confused on several areas of this. First, this is so obvious I am finding it hard to prove. Second, what are some definitions, axioms, or lemmas of an ll(k) grammar that I can use to build up a ...
0
votes
0answers
139 views

Can two distinct strings create the same parse tree for a given grammar?

More specifically: for any arbitrary CFG, is there guaranteed to exist two distinct strings such that a leftmost parse of both strings creates the same parse tree? If not, does there exist any CFG ...
0
votes
0answers
65 views

How to see if P is decidable semi-decidable, undecidable?

I've been trying to figure out a practice exam question, about if a given $P$. $P$ is the characteristics of recursive enumerable set given as: $$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\ ...
0
votes
0answers
31 views

Lossless Condensing, Modification, and Decondensing

Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where $f(\alpha)=\beta$, ...
0
votes
0answers
254 views

Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...
0
votes
1answer
259 views

Writing context free grammar

I have the following language: {0m1n0n1m | m,n ≠ 0} I was wanting to write Context-free grammar for it. I'm a little confused because the rule doesn't mention that m and n are not equal to each ...
0
votes
0answers
79 views

Growing context-sensitive grammars with context-free rules

Has anyone ever considered the class of languages $X$ generated by growing context-sensitive productions which are described by context-free rules? In particular, I wonder if there is a NP-complete ...
0
votes
1answer
60 views

How to check if my language is context-free can't seem to solve it using pumping lemma

I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to ...
0
votes
0answers
570 views

Describe the language generated by a given context free grammar

I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction. $$\begin{align} S &\to SA \mid \epsilon \\ A &\to aS \mid bA \...
0
votes
0answers
22 views

Grammar that generates a language with more “a” than “b” [duplicate]

I need to find a grammar that generates the language composed by all words that have more $a$ than $b$ given an alphabet $\{a,b\}$ I tried the following production rules: ...
0
votes
0answers
74 views

Linear time parsing from star of context free language

I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar: ...
0
votes
0answers
25 views

CFG. Ensure that $n\neq m$ twice in $L=\{a^m b^n c^m d^n, m\neq n\}$ [duplicate]

During the formal language exam, the professor allowed to find a CFG to following language: $\{a^m b^n c^p d^q, m\neq n\wedge p\neq q\}(1)$, because neither he saw a solution (He passed a test without ...
0
votes
0answers
24 views

Prove this language is not CFL [duplicate]

I have this language: $L = \{a^{n+2} b^m a^{2n} b^{3n}\mid n,m >=0 \}$ and I am trying to prove that it is not CFL. I assumed that my word is $a^{p+2} b^m a^{2p} b^{3p}$ (where $p$ is the pumpung ...
0
votes
0answers
111 views

Context-free with single terminal symbol — regular language [duplicate]

I have the following problem to solve: Show that if G is a context-free grammar and Σ consists of just one terminal symbol, then L(G) is regular. It is problem 4.26 from the book "Formal models of ...
0
votes
0answers
489 views

LL(1) grammar for the untyped lambda-calculus

What I want to do I am trying to define a LL(1) grammar of the lambda-calculus. What I did Here is the grammar: $Term \to Abs$ $Term \to App$ $Abs \to \lambda \ id \ . \ Term$ $App \to Var \ ...
0
votes
0answers
58 views

A context free grammar for the language of even-length non-palindromes [duplicate]

I am trying to find a context free grammar for the language $L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$ where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible ...
0
votes
2answers
225 views

generating recursive descent parser

I have a grammar, $L \to A \langle A \rangle^*$ $A \to () \mid (L)$ but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T \langle^*T\...
0
votes
1answer
230 views

Regular Grammar and Regular Language [closed]

From Wikipedia, Regular Language All finite languages are regular. and Also Regular Grammar, is a way to describe the Regular Language Right regular grammar (also called right linear grammar). Left ...
0
votes
1answer
29 views

Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$ [closed]

Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$. I just wanted to check if my grammar is correct or not. $$A \...
0
votes
0answers
61 views

Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

I have constructed an SLR(1) parsing table with the following rules. S -> S + S + S (rule 1) S -> S + S (rule 2) S -> y Is reducing rule 2, then shifting + and y, then again rule 2, equivalent to ...
0
votes
0answers
67 views

Designing CFG for sequences of words of which two arbitrary ones are reversals

Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because $...
0
votes
0answers
122 views

Making a regular grammar for this language

I'm trying to make a regular grammar for this language: Where the alphabet is $ \Sigma $ = $\{a,b,c\}$ It seemed like it would go well with a right-linear grammar. This may be disastrously wrong, ...
0
votes
0answers
37 views

Grammar that contains letters a,b,c and number of letters $c$ is greater than number of letters $b$ [duplicate]

I look for grammar which use letters $a,b,c$ that numbers of letters $c$ is greater than number of letters $b$. Example: $acbccba$ I thought about: $$S \rightarrow aS \mid bS \mid SCS$$ $$C \...
0
votes
1answer
2k views

CFG for $\{a^i b^j : 2 i<j\}$ [duplicate]

So I have a question: Give a CFG for $\{a^i b^j : 2 i<j\}$ And this is my approach: $S\to AB$ $A\to aAb\mid \varepsilon$ $B\to b \mid bB$ A confirmation, or correction, along with how you ...
0
votes
1answer
141 views

Context free grammar for {a^mb^n | m ≠ n} [duplicate]

I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$. This is what ...
0
votes
0answers
59 views

How i can use Mathematical induction to prove CFG production? [duplicate]

If I have production $G_n$ $S \rightarrow A_i b_i \quad$ for $1 \le i \le n$ $A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$ Prove $G_n$ is sub-productions from $2n^2 - n$ ...
0
votes
1answer
32 views

Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }. This is really confusing me, I'm having trouble with ...
0
votes
1answer
77 views

Construct a grammar for the language

How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must ...
0
votes
1answer
1k views

How to write an EBNF grammar for Java float literals?

I've got this question on my study guide: "Write an EBNF grammar description for Java float literals and one for Java double literals." I've browsed the Oracle site and found the grammar for java ...
0
votes
2answers
905 views

Context-free grammar for“not-at-all” palindromes

I need to bulid a context-free grammar for $\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$ Not palindrom at all: We will say that a word $w$ is not palindrome at ...