Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
-3
votes
0answers
31 views

Express L(G) in set notation

Consider the G grammar below. S ->aSa|A A ->bAb|B B ->ccB|λ Just want to express L(G) in set notation. Could some give me some ideas?
0
votes
0answers
30 views

Is this grammar in Backus–Naur form?

I'm a newbie and a paper I'm reading specifies the following grammar: ...
0
votes
1answer
450 views

LL1 parsing algorithm for strings generated by a given grammar

How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar? I have to design a parser for a specific grammar. Let $G$ be the grammar described as: $$S \...
0
votes
2answers
160 views

Context free grammar problem for number of a's is twice the number of b's

Can you to find for me a context free grammar for the following language? $$\{w\in\{a,b\}^*: \#_a(w)=2\#_b(w)\} $$ Here $\#_a(w)$ counts the number of $a$'s in $w$.
0
votes
1answer
29 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
0
votes
1answer
50 views

Converting PDA to CFG

I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
-3
votes
2answers
10k views

GATE CS 2009, question 11, does the grammar produce odd-length palindromes? [closed]

This is question 11 from GATE CS 2009. Find the language generated by the following grammar over the input alphabet = $\{a,b\}$. $S \to aSa \mid bSb \mid a \mid b $ The language generated by the ...
14
votes
1answer
450 views

Is the language of words that are unbalanced in the first half context-free?

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
0
votes
1answer
42 views

How to remove null production from context free grammar?

How to remove null production and simply the grammar? $$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$ Can the simplification result in this CFG? $$ S \to a \mid aBa \\ A \to ...
1
vote
0answers
49 views

Is every language described by a grammar?

I read the following argument showing that not every language is described by a grammar: For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
0
votes
1answer
23 views

If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?

I was studying automata theory and formal languages and came across this question: If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ? I've searched the theory but I am missing ...
0
votes
1answer
70 views

Enumerator for Word and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
0
votes
1answer
41 views
-1
votes
1answer
60 views

How to design a formal grammar to convert EBNF description to a list of CFG production rules

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm. Can CFG production rules is generated from an EBNF description by a rewrite ...
0
votes
1answer
47 views

Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$

Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and ...
0
votes
1answer
97 views

Removing left factoring from Context-Free Grammar

I know that, removing left factoring is a simple task. And i understand following procedure: $S→aA | aB$ Becomes: $S→aS'$ $S'→A|B$ Yet I'm running into problems with this particular grammar: $S→AD|...
0
votes
0answers
35 views

What is a make sense (meaningful) example of language that an unrestricted grammar could generate?

I have learned that: Unrestricted grammar is used to define (or describe) a formal language. Unrestricted grammar is used to define recursively enumerable set [https://en.wikipedia.org/wiki/...
0
votes
1answer
152 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
0answers
38 views

Turning grammar to LL(1)

I have difficulty / doubt in transforming a grammar into LL (1), I tried remove left recursion but grammar still not LL(1). ...
1
vote
1answer
47 views

Help with context free grammar excercise

So, I have an exercise in which I have to write a context free grammar for this language: $$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$ meaning every string with any ...
1
vote
2answers
1k views

Size of a context-free grammar

Is there a formal definition for a size of a context-free grammar? The only definition I have seen so far is on this wiki page: The size of a grammar is the sum of the sizes of its production rules,...
0
votes
0answers
24 views

Is there any good method to find if a grammar is optimal for a problem?

I've been thinking about grammatical evolution problems and how the grammar influences the algorithm performance. It came to my mind the huge impact that the grammar that you're using has in the time ...
0
votes
2answers
35 views

removing indirect left recursion

I want to remove indirect left recursion from these rules: S-->TU, T-->US|b, U-->ST|a I don't know if I can implement the algorithm correctly. ...
3
votes
0answers
44 views

Are there context free grammars for all restricted Dyck paths?

A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...
-1
votes
1answer
17 views

How to simplify context free grammar?

How to simplify this context-free grammar into a similar one with no unit productions and no useless symbols? $$ S \to ABA \\ A \to aAA \mid aBC \mid bB \\ B \to A \mid bB \mid Cb \\ C \to CC \mid cC ...
0
votes
0answers
57 views

What does it take to create a new programming language and its toolchain?

I am super novice to this topic, so my apologies if my question looks completely nonsense to you all! Imagine you want to create a new programing language that transpiles to a more common high/low-...
0
votes
0answers
25 views

Upper bound on size of derivation in CFG

Suppose $G$ is a $CFG$ with $m$ variables, in which the right-hand side of all production rules has length at most $\ell$. Show that if $A\Rightarrow^*_G\varepsilon$, then there is a derivation of no ...
1
vote
1answer
376 views

What are the modern alternatives to Backus–Naur form and what are their advantages?

I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of ...
1
vote
1answer
197 views

What are the known ambiguities in C language grammar?

I have found this reference for the C syntax Backus-Naur Form (BNF). I was wondering if there are any other ambiguities in this grammar other than the infamous "dangling else"? Also how we ...
0
votes
1answer
16 views

Predicitve Parser LL(1) condition

Lets say we use the predictive parser LL(1). Why is it necessary that $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$, for all $\alpha, \beta$ right side of alternative productions i.e., productions ...
0
votes
2answers
49 views

Is this an LL(1) grammar? How to solve First - Follow conflict?

im trying to check if this grammar is LL(1). S -> L = R L -> * L | id R -> L | R + R | num As you can see there is a Left recursion on R production. So i remove that and what i get is: S -> L = ...
2
votes
1answer
727 views

CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s}

I know the answer which is: \begin{align} S &\rightarrow aS \mid T\\ T &\rightarrow aTbT\ \mid \varepsilon \end{align} Now, $bbaaa$ is in the language. But the given CFG cannot generate it. ...
0
votes
1answer
35 views

Is this grammar LL(1) grammar?

Is this grammar LL(1)? Would it be a problem that S can be both E/S and E? S -> E / S S -> E E -> letter E -> ‘ S ’ Can it derive ‘a / e / ‘g / s’ ’...
2
votes
1answer
33 views

Is s-grammar powerful enough to generate all possible DCFL?

In s-grammar all productions are in form of A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V* "... and any pair (A, a) occurs at most once in P." [P. Linz, 6th ed. , p. 144] s-...
1
vote
1answer
23 views

Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages)

I want to stress that i am not looking for a proof of this question, but rather if someone(that is familiar with the proof and it's context) can explain to me what the symbol 'e' means in the context. ...
0
votes
0answers
29 views

How to determine if a language produced by grammar is recognizable by deterministic pushdown automaton (DPDA)? [duplicate]

I have a following grammar: S -> aSa | bSb | $\lambda$. And I have to figure out whether the language produced by this grammar is recognizable by DPDA. I can't find any theorems about it. Obviously, ...
0
votes
0answers
16 views

Redcue CFG-Eequiv to CFG-SYM [duplicate]

I want to show, that for an CFG G the question wether $L(G)=L(G)^R$ is undecidable. My first try was to reduce from the CFG-Equivalent Problem) $CFG_{EQUIV}\leq CFG_{SYM}$. My first attempt was to ...
0
votes
2answers
1k views

Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$

I want to build a context sensitive grammar for the language $\{a^{2^n}\mid n\geq 0\}$. I think it should be something like this \begin{align*} S &\to aA \mid a\\ aA&\to aaaA \mid aa \end{...
0
votes
0answers
24 views

Counting the number of unique syntax trees of a grammar

Lets say we have some arbitrary grammar for which we would like to know how many different syntax trees does it generate. For example the following: S -> A1|1B A -> 10|C B -> C1 | $\varepsilon$ C -...
0
votes
0answers
55 views

context-free language : if yx belongs to cfl then xy is also cfl [duplicate]

I faced a problem. What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language. C is a Context-Free Language. I think we can use the PDA ...
0
votes
1answer
32 views

Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }. This is really confusing me, I'm having trouble with ...
1
vote
1answer
43 views

What complexity class is this set of grammars? In between NL and P?

Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals ...
-1
votes
1answer
29 views

How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A

Let us consider the following Context-Free Grammar G = ({S,A,B,C,D},{a, b}, S, P) with production rules P: S → SSA | Bb A → BSA B → A | Cb C → AD | Cb | ɛ D → a | b | ɛ Let L be the language ...
1
vote
2answers
2k views

Why is this grammar an LL(2) grammar?

I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why. $$L = \{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,...
4
votes
2answers
24k views

How to convert PDA to CFG

I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG? For example: to write CFG for the automata My attempt: $S=A_{03}$ because $...
0
votes
2answers
41 views

Regular expression for a palindrome of finite length?

I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$ I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
3
votes
1answer
111 views

Why is this language a regular language?

Came across this in a book, and I'm wondering why the following language is regular? $$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$ Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
1
vote
1answer
37 views

How to create a regular expression for this language?

I have a language: $$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$ I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
-2
votes
1answer
35 views

Grammar with a long derivation generates an infinite language

Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$ generates some string with a derivation having at least $2^b$ steps, then $L(G)$ is infinite. This question is ...
1
vote
0answers
36 views

How to generate a DFA that recognizes a non-regular Grammar

How would you convert the following grammar to a DFA that recognizes its language? \begin{align} &G = (\{S,A,B\},\{0,1\}, S, P)\\ &P\colon &&S\rightarrow A1B\\ &&&A \...

1
2 3 4 5
21