We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
-1
votes
1answer
1k views

Proving correctness of a CFG by induction on length of strings generated [duplicate]

Consider the following grammar with starting symbol of $S$. $$S \rightarrow 0S11\;|\;S1\;|\;0$$ Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all ...
-1
votes
1answer
113 views

Representing grammar for list/dictionary with optional end separator as LL(1)

Considering a grammar that includes a dictionary or list with an optional terminal separator - e.g.: $$ \begin{align} obj \to & dict \\ &\mid OTHER \\ dict \to & \...
-2
votes
1answer
154 views

Is the set of strings $0^{2k}10^{2k}10^{k}$ for $k \geq 0$ context-free?

I am able to solve $0^{k}10^{k}10^{j}$ where $ k < j$. and I was able to see that this is also a concatenation of two strings. How to do it for $0^{2k}10^{2k}10^{k}$ for $k \ge 0$?
-2
votes
1answer
723 views

Generative grammars and analytic grammars?

What are a generative grammar and an analytic grammar? How are they different from a formal grammar? Is the recursive definition of the language of a propositional calculus, a first order logic ...
-2
votes
1answer
55 views

Provide “regular” grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$} [duplicate]

I'm trying to understand the approach to constructing an grammar which accepts the language ${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$ } Thanks.
-2
votes
1answer
51 views

Find grammar for the following language: $\{ a^{m_1}ba^{m_2}b\dots a^{m_k}bca^n \mid m_j = n \text{ for some } 1 \le j \le k \}$

I need to Find grammar for the following language: $\{ a^{m_1}ba^{m_2}b\dots a^{m_k}bca^n \mid m_j = n \text{ for some } 1 \le j \le k \}$. can someone help me to solve it? I am not sure how to start....
-2
votes
1answer
118 views

$L = \{ w \in \{0, 1, 2\}^*: |0| + |2| = |1| \}$ where |0| denotes number of 0s in the string w

I have come up with: S→0SX | 1SY | 2SZ | SS | ϵ X→1 Y→0 | 2 Z→1 I think I am wrong. Any directions?
-2
votes
1answer
39 views

Context free languages [closed]

I have stumbled on this question: Which of the following languages over the alphabet ${a,b,c,d}$ are context-free and which not ? a) $L_{1} = \{wa^{3n+1}b^nw^{R} \mid w\in \{c,d\}^*,\ n>0\}$; b)...
-2
votes
1answer
114 views

What's the step for build a SLR table for the following CFG? [closed]

(r1) E → E+T (r2) E → T (r3) T → T F (r4)T →F (r5) F → F∗ (r6) F → a (r7) F → b I am just doing the exercise on the workshop. I just knew how to the build the SLR state machine for this CFG. ...
-2
votes
2answers
72 views

Analysing a context-free grammar

Let: $$S \to AC \mid BC\\ A \to aAb \mid aA \mid a\\ B \to aBb \mid Bb \mid b\\ C \to Cc \mid c$$ I need to find if: the word $aabbbcc $ is in the grammer, and if so to write a very left series, ...
-2
votes
1answer
136 views

Getting the context free grammer

I am trying to get the a CFG for this. I got this: L1={uv | u ∈Σ∗,v∈ Σ∗1Σ∗ and |v| ≤ |u|} ...
-2
votes
1answer
526 views

CFG for all string that don't end at ba?

Here is my solution: S-> Sab|Sbb|Saa S->aS S->bS S->ε Is this solution right?
-2
votes
1answer
222 views

Pushdown Automata Challenge

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ aB->aS|$\...
-2
votes
1answer
88 views

Language of a grammar

What's the language of following grammar? $G: S \to S_1B$ $S_1 \to aS_1b$ $bB \to bbbB$ $aS_1b \to aa$ $B \to \lambda$ any hint or solution?
-2
votes
1answer
161 views

Find an unambiguous grammar [closed]

S → aS | aSbS | (empty) where the alphabet is {a,b} in other words, the set of strings where any prefix has at least as many 'a's as 'b's.
-2
votes
1answer
59 views

How do I define a language from a grammar?

Given an alphabet $ Λ = \{a, b, c\}$, I have the following grammar: $$ S -> aSb | aAb $$ $$ A -> aaA | aBb $$ $$ B -> Bbb | c $$ Which method should I use to write the definition of the ...
-2
votes
1answer
365 views

How should I show that a grammar is not LL(1) and convert grammar to LL(1)

I'm trying to find the ambiguity in this grammar so I can remove it and convert it to LL(1), however for the life of me, I can't find the ambiguity. Moreover, I think there is cycle between X and Y ...
-3
votes
2answers
152 views

Grammar for a language with 1/3 of a's

I have this language: $$ L = \left\{ w \in \{a,b,c\}^* \;\big|\; |w| / |w|_a = 3 \right\} $$ where $|w|_a$ is the number of occurrences of $a$. How can I find a grammar that generates it?
-3
votes
2answers
9k views

odd length palindrome's f=language [closed]

Find the language generated by the following grammar over the input alphabet = {a,b}. S –> aSa | bSb | a | b The language generated by the above grammar over the alphabet {a,b} is the set of (A) ...
-3
votes
2answers
73 views

Show that each of these languages is decidable for regular grammars [closed]

Show that each of these languages is decidable for regular grammars by presenting a clear algorithm for each. In each case, assume is the encoding of a regular grammar as a string and L(G) is the ...
-3
votes
1answer
87 views

CFG for $L=\{w_1cw_2:w_1\neq w_2^{R}\}$

I am trying to construct a context-free grammar for the following language: $$L=\{w_1cw_2:w_1\neq w_2^{R}\},$$ where words are over $\{a,b,c\}$. I have tried to do this by taking the union of two sub-...
-3
votes
1answer
76 views

Chomsky Normal Form of |a|<|b| [closed]

Hello Everyone I was hoping I could ask you to check to my work on this CNF, These are a pain to me and I want to make sure I'm doing it right the first time ...
-3
votes
1answer
2k views

Eliminating Null Productions from Context Free Grammar

Here is a problem I am trying to solve: S -> 0A0 | 1B1 | BB A -> C B -> S | A C -> S | e I know that C is nullable (since it produces an epsilon) and ...
-3
votes
1answer
88 views

What is the language generated by the following grammar? [closed]

Could please tell me the language generated by this grammar? S->iS |iSeS|ε
-4
votes
1answer
419 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.