1
vote
1answer
85 views

Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$

could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$
-3
votes
1answer
94 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$ ...
0
votes
2answers
39 views

Are constituency grammars and dependency grammars two different types of context free grammars?

From http://en.wikipedia.org/wiki/Parse_tree A concrete syntax tree or parse tree or parsing tree[1] or derivation tree is an ordered, rooted tree that represents the syntactic structure of a ...
-3
votes
1answer
61 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?
1
vote
1answer
41 views

Are all Chomsky-Type3 grammars LL(1)?

Referring to this Question, where an answer is stating that all Type 3 languages are LL(1), I'd like to know if all Type 3 grammars are possibly LL(1). If not, why is it so? Are there maybe ambiguous ...
-2
votes
1answer
39 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 ...
1
vote
1answer
75 views

What are the meanings of metalanguage and metasyntax and EBNF?

I am trying to understand what BNF, metalanguage, and metasyntax are. From https://proofwiki.org/wiki/Definition:Metalanguage A metalanguage of a formal language is a formal language used to ...
-5
votes
1answer
34 views

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

Could please tell me the language generated by this grammar? S->iS |iSeS|ε
-3
votes
2answers
79 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
98 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
5
votes
2answers
472 views

does every CFL have an ambiguous CFG?

some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states: Many [context ...
1
vote
1answer
102 views

Resolve left-rescursion

Can anybody give me a hint on how to get rid of the left recursion in the following grammar? $$A \rightarrow B \mid a$$ $$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$ $$C \rightarrow c \mid A ...
3
votes
0answers
43 views

Automatic tool for resolving left-recursion within CFG [closed]

Though facing the fear that someone might not like my question but does somebody know a useful tool to either resolve left recursion or to simplify a context-free grammar automatically ? I need ...
1
vote
2answers
121 views

Syntax and formal grammar of a formal language

For a formal language, I wonder what differences and relations are between its syntax and its formal grammar. A formal grammar is a set of formation rules that describe how to generate the strings ...
-1
votes
1answer
31 views

Construct grammar given the following language [duplicate]

Construct grammar given the following language! $ L = \{(ab)^{n+1}u(ba)^n|n>0, l_c(u) = 1, u\in\{a,c,d\}^* \}$ My interpretation in a less accurate way: $(ab)^{n+1}$ says we need to concatenate ...
0
votes
1answer
35 views

Is my grammar correct for this context-free language?

$\{a^nb^2a^n \mid n \ge0\}$ I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between. I came up with ...
3
votes
0answers
55 views

Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution

Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally ...
1
vote
1answer
61 views

Constructing an unrestricted grammar for a^n b^m c^n d^m [closed]

I've been trying to construct an unrestricted grammar which has the language: L = {a^n b^m c^n d^m | n>0, m>0} But I can't seem to figure it out without ...
3
votes
1answer
100 views

A Question from Introduction to Formal Languages by Gyorgy E. Revesz; Exercise 1.1

The exercise says "Show that the grammar $G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$ generates the language $L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$." Now, I'm new to ...
1
vote
1answer
51 views

How to check ambiguity of a specific grammar

Giving the following Grammar: S → ^ | SaSMSM | SMSaSM | SMSMSa M → b | c ^ means eopsilon. How can i check whether its ambgious or not? My intuition is ...
0
votes
2answers
78 views

Find a CFG for a language

In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p ...
3
votes
2answers
264 views

Proving that a word is *not* generated by a context-free grammar

I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF... How did they get the answer so that ab ...
2
votes
0answers
93 views

Good introductions to Formal Language Theory and Formal Grammars

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In ...
3
votes
3answers
86 views

Compression of non-adjacent structure using grammar

I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string ...
3
votes
1answer
40 views

grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)

Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are ...
1
vote
3answers
254 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
1
vote
2answers
244 views

Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ [closed]

I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$ $$L=\{a^nb^m\mid 2n<m<3n\}$$
0
votes
1answer
29 views

Construct context free grammar from language

I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific: $\lbrace ...
3
votes
2answers
111 views

Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
1
vote
0answers
45 views

Designing a different grammer that generates same expression [duplicate]

I've a set of grammar rules like this: $$ \begin{align*} &S \to AbB \\ &A \to aA|\epsilon \\ &B \to aB|bB|\epsilon \end{align*} $$ The grammar generates the following words: $$ ...
2
votes
0answers
41 views

What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
-1
votes
1answer
87 views

Left Linear Grammar: How to construct?

I need help constructing a Left Linear grammar for the language $L = \{ a^n b^m c^p \mid n\geq 2, m\geq 3, p\geq 4 \}$ Here is what I have so far, I know : $N = \{S\}$ $T = \{ a, b, c \}$ $P = ...
0
votes
1answer
91 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
2answers
84 views

Is $a^{n+m}b^{n}c^{m}$ context free?

Language: $ L = a^{n+m}b^{n}c^{m} $ As per a recent test I gave, this language is not context free. However, I think it is. Corresponding Grammar: $ X \rightarrow aXY \space |\space \epsilon $ $ ...
0
votes
0answers
41 views

Find the language generated by a grammar

I have to find the language generated by the grammar: $\qquad\begin{align*} S &\to SA \mid a \\ A &\to aAa \mid bA \mid \varepsilon \end{align*}$ where $\varepsilon$ is the empty ...
0
votes
0answers
18 views

Unambiguous Context free Grammar [duplicate]

I was reading through Context Free Grammar, and I came across ambiguous grammar. If the language produced by CFG has more then 1 parse tree, then CFG is an ambiguous grammar. Is there any way by which ...
0
votes
0answers
53 views

Is this a grammar for arithmetic expressions?

Describe the language generated by the following grammar <A> ::= <A><A> '+' | <A><A> '*' | 'a' So it's not too hard to see ...
6
votes
1answer
174 views

Why is ww a linear indexed language while www is not?

I am a little bit confused on one idea regarding indexed languages. $\{ww \mid w \in \{a,b,c\}^* \}$ is a linear indexed language, but $\{www \mid w \in \{a,b,c\}^* \}$ is not a linear ...
3
votes
2answers
184 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
0
votes
1answer
136 views

Is this language context free?

In a recent test, I was asked to recognize if the below language is context free: $\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$ I think it is context free, and can be accepted by ...
1
vote
0answers
36 views

Is this theorem about left-factored grammars correct?

I am working on CFG grammars, LL grammars in particular and I encountered the following theorem in the slides of presentations written by my professor: A CFG grammar cannot be left-factored if all ...
0
votes
0answers
14 views

step-by-step approach context free grammar [duplicate]

can someone give me the step-by-step approach to obtaining a context free grammar for a language? example: obtain a grammar to generate string consisting of at least 2 a's my answer was this: S-->aA ...
6
votes
1answer
199 views

Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
2
votes
1answer
268 views

Is $\{a, b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$ context-free?

Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not? ...
0
votes
0answers
42 views

Write grammars rule to translate general boolean expressions in Prodocut Of Sums

Given a standard grammar describing the boolean expression with AND, OR and NOT operators: ...
2
votes
1answer
48 views

“Grammar inference” for 2-D images

Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in ...
8
votes
2answers
290 views

How to prove that a language is context-free?

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...
0
votes
2answers
267 views

CFG for $\{a^ib^jc^k \mid i \neq j+k\}$

I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq j+k\}$ over the alphabet $\Sigma = \{a,b,c\}$. I know that I can split this up into the union of two cfg's ...
0
votes
0answers
61 views

Does this CFG produce this language?

I missed a question about a CFG on an assignment, but the grader wouldn't explain what was wrong with my answer and instead provided me the answer from the book. Here is the language: ...
1
vote
1answer
117 views

Is my proof for a context free language correct? Same number of a's as b's

I have the following grammar G: $$ \begin{align*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align*} $$ I am going to prove that this language L(G) consists of words with the ...