Questions about formal grammars, generative descriptions of formal languages.

learn more… | top users | synonyms (1)

2
votes
2answers
128 views

Can this language be defined by a Context Free Grammer?

I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt: Question: $L = \{a^n b^m c^p \mid n = m + ...
0
votes
1answer
41 views

Computing FIRST and FOLLOW sets

Suppose we have the following grammar: S -> A ( S ) B | ε A -> S | S B | x | ε B -> S B | y where S is the start ...
-1
votes
1answer
22 views

Chomsky Normal Form-remove unit production

In the step of removing unit productions when converting a grammar to Chomsky normal form, I sometimes found that the variables may end up having the same production bodies. Is this possible? If so, ...
0
votes
0answers
20 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
1answer
38 views

How can I prove this language is not CFL? [duplicate]

I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m ...
0
votes
0answers
107 views

For which subset of all CFG can we show that $L=\mathcal{L}(G)$

Raphael explained in the comments that there are no algorithms to show $L=\mathcal{L}(G)$ for context-free grammar. So we have to reduce our expectations and try to find a proof method. In this ...
-1
votes
1answer
27 views

What would be CFG for all strings which does not contain bbb?

Is there a way to get complement? Following is my solution for CFG of all strings that DON'T contain bbb. ...
-2
votes
1answer
29 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?
1
vote
0answers
45 views

How to convert CFG with Kleene Star, Kleene Plus, and Question Mark to Chomsky Normal Form?

I am fairly new to formal language theory but understand how to convert simple CFGs into both Chomsky normal form and Greibach normal form. However, I have not seen any examples of how to do that when ...
3
votes
1answer
52 views

Removing left-recursion in grammar while maintaining left-association of operator

I have a problem with this exercise: Let G be the following ambiguous grammar for the λ-calculus: E → v | λv.E | EE | (E) where E is the single ...
1
vote
2answers
90 views

Tips for creating “Context Free Grammar” [duplicate]

I am new to CFG's, Can someone give me tips in creating CFG that generates some language For example $L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where $w^R$ is the reverse ...
20
votes
2answers
2k views

What does “context” in “context-free grammar” refer to?

There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble: What context is it free of? To investigate, I Googled "context ...
0
votes
0answers
36 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 ...
-3
votes
1answer
28 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 ...
0
votes
1answer
21 views

Identity productions in regular grammar

If a grammar is of the following form (i.e. all its productions are), is its language regular? $B → a$ - where $B$ is a non-terminal in $N$ and a is a terminal in $Σ$ $B → aC$ - where $B$ and $C$ ...
5
votes
1answer
87 views

Closure properties of linear context-free languages

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, ...
6
votes
4answers
263 views

Relationship between formal system and formal languages

In a course of computer science it is common to study the hierarchy of formal languages, grammars, automata and Turing machines. I wonder what is the relationship of these objects with formal systems. ...
4
votes
1answer
61 views

Language of walks in a grid – context-free?

Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square ...
-1
votes
1answer
26 views

Eliminate Left Recursion

The part I want to modify: B -> F | B A | A What is the correct way to remove this left recursion? I was thinking ...
1
vote
1answer
56 views

Removing Left Recursion

Im currently learning about removing left recursion. Ive watched a few youtube clips and understand the basics. For example, i can remove left recursion for the following; $E \rightarrow E+T \mid T$ ...
0
votes
2answers
21 views

How would I write a single expression involving count, x and y that has exactly the same effect as shown (below)? [closed]

count=0 x=7 y=3 while(y<x): y+=1 count+=1 I'm having trouble writing this as a single expression.
2
votes
2answers
128 views

Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$ [duplicate]

I'm having trouble constructing a Context Free Grammar for the following language: $$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$ I believe it's telling me that no string can be ...
2
votes
1answer
28 views

Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?

Consider a grammar G which is SLR(1) except for some shift/reduce conflicts which can be resolved by imposing some precedence or associativity of operators. Is it the case that the construction of ...
2
votes
1answer
108 views

What is a real-world use-case/need for a left-recursive grammar?

I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as: ...like LL and LR parsing, PEGs are often frustrating to use in ...
4
votes
1answer
39 views

Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$

I would like to get some help for finding the context-sensitive grammar for the language: $$L_1=\{a^ib^jc^{ij} \mid i,j\geq 0\}.$$ To answer the question before it's written here, yes I've tried to ...
2
votes
2answers
42 views

Ambiguous context free

Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.
1
vote
0answers
31 views

Is $\{u\#v \mid u\not=v\}$ context-free? [duplicate]

Is the following language context-free? $$ \{u\#v\in\Sigma^* \mid u\not=v \text{ and } u,v\in\{0,1\}^*\} $$ You can assume $\{0,1,\#\}\subseteq\Sigma$. Unnecessary background information: I am ...
3
votes
1answer
96 views

Difference between substitution, morphism, and homomorphism

In closure properties, I got confused between substitution and morphism. 1) According to wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a ...
0
votes
2answers
49 views

Converting regular (Type-3) grammar to a deterministic finite state automaton

I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to ...
0
votes
0answers
15 views

CFG for language [duplicate]

I'm trying to create CFG for a language. The language is following: {w | {a,b}* | w should have one more a than there are b: s } I built following grammar: S -> aB | aSb | bSa | abS | baS | Sab | ...
0
votes
0answers
55 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 \ ...
1
vote
1answer
53 views

Is this grammar LR(1)?

A bit confused about whether this grammar is ambiguous or not C' -> C C -> d C u C C -> d C C -> ε I tried building the DFA for this but I get this ...
0
votes
0answers
36 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 ...
1
vote
1answer
51 views

What is the complement of ACFG

What is the complement of $\mathrm{ACFG} = \{ G \mid G \text{ is a CFG and }L(G) = \Sigma^* \}$? I think it is $\mathrm{ECFG} = \{ G \mid G\text{ is a CFG and }L(G) = \emptyset \}$. It makes sense ...
0
votes
0answers
31 views

from not LR(0) grammar to LR(0) grammar

Question from an exam: Given the grammar, $$\begin{align*} S&\to E\$\\ E&\to \mathrm{id} \mid \mathrm {id}(E) \end{align*}$$ Construct a grammar of the same language that ...
1
vote
0answers
228 views

Converting Chomsky Normal Forms to Greibach Normal Form

Here is a passage from Kozen's Automata and Computability (pages 145-146) that I'm confused about: Now we show how to convert an arbitrary grammar to an equivalent one (except possibly for $ ...
0
votes
1answer
40 views

How to create an LR($k$) grammar for a given language?

How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say: $$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = ...
0
votes
2answers
44 views
0
votes
0answers
89 views

How to convert the following grammar to LL(1)?

The following grammar is given: \begin{align*} M &\rightarrow d M d \\ M &\rightarrow e M e \\ M &\rightarrow f M f \\ M &\rightarrow \varepsilon \end{align*} I've checked it with ...
2
votes
1answer
115 views

Is equivalence of a CFG and an RG undecidable?

I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?
-1
votes
1answer
50 views

Some Algorithm on Decidablitly [closed]

Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description? There is an algorithm that decides whether the ...
0
votes
2answers
36 views

Erasing $\epsilon$ production from CFG

I would like to delete the $\epsilon$-production from the context free grammar with the following rules P: $$S \rightarrow ASB , BSA, \epsilon$$ $$A \rightarrow aS$$ $$B \rightarrow bB, b$$ Now we ...
4
votes
1answer
36 views

Method for Creating Any Unambiguous Grammar?

I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that Was guaranteed to produce ...
2
votes
2answers
132 views

Can there be two different left most derevations for a grammar?

Suppose there is a CFG with the rules S--> Aa A--> Bb B--> A B--> Epsilon To my best understanding the left most derivation would go like this.. ...
0
votes
2answers
62 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 ...
2
votes
0answers
62 views

Removing hidden ambiguity in grammar using left factoring

I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new ...
1
vote
1answer
37 views

Generate Regular Grammar for a Language with Modular Condition

This is a homework problem. I've wrestled with it for quite awhile and can't come up with a valid solution. The problem is: Find a regular grammar that generates each of the following languages: ...
2
votes
1answer
115 views

An example of a non-regular grammar for a regular language?

I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?
1
vote
1answer
90 views

Relaxation of the null production restriction in Regular and Context Free Grammars

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
1
vote
1answer
68 views

Is it Regular Language?

According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite .. that's mean it may be ...