1
vote
1answer
38 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
50 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
218 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
55 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
72 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
35 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 ...
0
votes
3answers
145 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
0answers
34 views

A construction to show a very restricted substitution closure result for DCFLs

Let $P$ be a deterministic PDA recognizing a deterministic CFL with a binary alphabet. Modify $P$ to identify its reading states (denote this subset of states by $R$) in accordance with the ...
1
vote
2answers
99 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
24 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
81 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
44 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
38 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
34 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
64 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
78 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
39 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
13 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
44 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
164 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
157 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
130 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
32 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 ...
3
votes
1answer
109 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
214 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
35 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: ...
3
votes
1answer
41 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 ...
5
votes
1answer
148 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 ...
-1
votes
3answers
95 views

Finding an LL(1) grammar? [closed]

How would I find an LL(1) grammar for the language: L=am bn cm+n Where m and n are elements of the naturals? My context-free grammar is: S → aSc | B B → bBc | A A → ...
0
votes
2answers
178 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
55 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
103 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 ...
3
votes
3answers
124 views

Designing a CFG that produces as many c's as the difference of numbers of a's and b's

The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is $\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in ...
0
votes
1answer
43 views

Reducing states of a GTG

I used this generalized transition graph with 3 states and got an equivalent generalized transition graph with 2 states: GTG: Equivalent with 2 states: I'm not sure about the regular ...
2
votes
1answer
56 views

Regular Expression as basis for creating this grammar

I made a right-linear grammar from a regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^{*}(ba)^{*}bb$ My solution, it seems a little too short like I'm leaving ...
1
vote
1answer
71 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
2answers
76 views

Equivalence of Context-Free-Grammar and Context-Free-Grammar in CNF

Given any Context-Free-Grammar, $G$, and another in Chomsky Normal Form, $G_c$, how can we check if both $G$ and $G_c$ generate the same language? One of the trivial ways I know of is to convert ...
2
votes
2answers
76 views

Class of a Language [duplicate]

What are the common ways to check if a given language is regular, context free, or context sensitive? Any surveys or notes would also be helpful. There's no need to describe your suggestions. eg. it ...
1
vote
2answers
202 views

Does this language have a context-free grammar?

Here is a question that I encountered in one of my exams: Find one context-free grammar that recognizes the language: $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\} $ Can you find such a ...
3
votes
3answers
133 views

Formal language without grammar

Definitions: Alphabet $Σ$: finite, non-empty set Language: subset of $Σ^*$ Grammar: Unrestricted grammar (Chomsky Type 0) Language of a grammar: all words that can be produced by applying $P$ ...
6
votes
3answers
146 views

Context-sensitive grammar for the language of words concatenated with themselves

I'm looking for a context-sensitive grammar that describes the following language: $L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ . I've got problems with the fact that no rules such as $X \to ...
1
vote
1answer
217 views

Does the empty language have a CFG in CNF?

I just not sure does empty set have a context-free grammar in Chomsky normal form? That is, for $B=\emptyset$, then a context-free grammar is $S \to S$, I think which doesn't have a Chomsky normal ...
2
votes
1answer
277 views

Is this formal grammar context-free (CFG) but not context-sensitive (CSG)?

I have the following formal grammar: $$G= (\{S,A,B\},\{a,b\},R,S)$$ $$R=\{S \rightarrow A\ |B, A \rightarrow \varepsilon\ | aA\ |bA, B \rightarrow \varepsilon\ |Bb\ | b\}$$ Now, we see, the ...
2
votes
2answers
89 views

Proving that CFLs are closed under even-ness using grammars

This is a question from a 2007 exam paper for a course I'm studying, question 2 on page 2. Theorem: Let $L$ be a context-free language. Let $L_{even}$ be the subset of $L$ consisting of all the ...
2
votes
1answer
166 views

What does the R superscript notation mean in regular/formal languages?

What does the capital R superscript notation mean in regular languages? I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means. For ...
1
vote
1answer
91 views

CNF: Recursion in CFG

How can I deal with recursive terminals in CFG when converting it to CNF? For example, S -> MN M -> AM | A N -> BN | B A -> a B -> b How can I reduce terminals M and N?
2
votes
5answers
203 views

Grammar that numbers of letters `c` is greater than number of letters `b`

Exactly as stated in the subject. I look for grammar which use letters $a, b ,c$ that numbers of letters $c$ is greater than number of letters $b$. Example: $acbccba$ is generated by the grammar. I ...
0
votes
2answers
60 views

Can this grammar be simplified?

So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has: $$ \begin{align} S &\rightarrow 0BS2 \mid 012 \\ B0 ...
3
votes
1answer
395 views

How to show that L = L(G)?

Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...