Questions about formal grammars, generative descriptions of formal languages.

learn more… | top users | synonyms (1)

1
vote
1answer
27 views

Does removal of unit production from the grammar may increase number of total production?

I have doubt ! Problem is There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions) (a) O(m) ...
2
votes
1answer
50 views

Equivalence in finite sets of turing machines

I have this exercise and I really don't know how to complete it: ...
2
votes
1answer
103 views

Difference between regular expression and grammar in automata

I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to ...
0
votes
1answer
50 views

How to construct a grammar that generates language L?

I'm in a Formal languages class and have a grammar quiz coming up. I'm assuming something like this will appear. Consider the alphabet $\Sigma$ = {a, b, c}. Construct a grammar that generates the ...
1
vote
1answer
41 views

Whats Wrong with this LL(1) Grammar?

I am trying to build a LL(1) parse table for the following Grammar: S -> L L -> L : L L -> id R R -> ( L ) R -> ( ) R -> Epsilon There are two Problems here. First the L rules are a left recursion ...
3
votes
1answer
27 views

Equivalence of two context free grammars [for the given example]

I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck: G1: S->e|aB|bA ...
3
votes
1answer
24 views

Arden's lemma applicability on context free grammars

The Arden's lemma states that there exists a solution to the equation between regular expressions r = sr + t, with r unknown, and it is s*t. I went through some other topics on the forum and I always ...
-2
votes
0answers
16 views

Practical Applications of theory of computation [closed]

Apart from compiler design, what are the various fields in which theory of computation is used. As this subject is often called mother of Computer Science
0
votes
1answer
24 views

Chomsky NF or Greibach NF benefits for LR parser?

Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind: total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating ...
0
votes
1answer
28 views

Can I couple non-terminals in context-free grammars?

If I had productions like so... $S \rightarrow A1B$ $A \rightarrow \epsilon$ $A \rightarrow 0$ $B \rightarrow \epsilon$ $B \rightarrow 1$ If I only want strings $\{\epsilon1\epsilon, 011\}$, am ...
1
vote
2answers
52 views

How to read BNF syntax of C?

Today I heard of BNF which is a language for languages. Also heard that it specifies the entire syntax of C in four pages. So I thought of checking it out. After reading through this page, I got a ...
0
votes
0answers
34 views

Can we remove unit productions First Before removing Null productions?

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...
6
votes
4answers
61 views

Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$

I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$ The size of a grammar is defined as the total length of all right-hand ...
2
votes
1answer
32 views

Inducing a context free grammar [closed]

I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?
0
votes
0answers
22 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 ...
2
votes
2answers
142 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
62 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
38 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 ...
-1
votes
1answer
28 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
31 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
50 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
70 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
100 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 ...
21
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
0answers
13 views

Chomsky Normal Form |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
92 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
308 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
67 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
28 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
69 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
24 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
146 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
35 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
117 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
41 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
48 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
34 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
121 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
62 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
61 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
54 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
52 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
35 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 ...