Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,020
questions
0
votes
0answers
13 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
38 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 ...
-2
votes
1answer
45 views
Show that grammar is ambiguous and remove ambiguity
Show that the following grammar is ambiguous:
\begin{align}
&S\to a \mid abSb \mid aAb \\
&A\to bS \mid aAAb
\end{align}
and covert into an unambiguous grammar.
0
votes
1answer
27 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
votes
1answer
16 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
54 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
22 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
353 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
188 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
15 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 ...
2
votes
1answer
32 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.
...
13
votes
1answer
421 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
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, ...
-1
votes
0answers
28 views
What is the language generated by grammar G?
I can't find what is the language generated by the grammar which has the below productions.
$$S\to AB|\epsilon$$
$$A\to aB$$
$$B\to Sb$$
I have reduced it to $S\to aSbSb | \epsilon$. But I cannot ...
0
votes
0answers
15 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
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
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 ...
3
votes
1answer
100 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 ...
0
votes
2answers
39 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 ...
1
vote
1answer
35 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 ...
0
votes
1answer
22 views
how to formally arrive at a correct EBNF grammar of a language
I am trying to write a mini parser for a simple language whose specification is as follows:
A search term is represented by. Both searchkey and ...
-1
votes
1answer
26 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 ...
0
votes
2answers
46 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 = ...
0
votes
2answers
51 views
Is it possible to design a Turing Machine without extra symbols for this language?
Is it possible to design a Turing Machine for the language defined as L = {0n1n | n >= 0} with only the symbols in the set of {blank, 0, 1}?
1
vote
1answer
43 views
Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$
I try to find a context free grammar for the language $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$. There is a hint ...
0
votes
2answers
62 views
Is the following language is a context free grammar language?
The question is to determine whether L is a context free grammar language, what do you think?
2
votes
2answers
83 views
Unambiguous context-free grammar for strings with at least as many a's as b's
I have designed this Grammar but it is ambiguous:
$$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$
Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.
0
votes
0answers
40 views
Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?
I am supposed to find an algorithm solving the following problem:
Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$.
...
1
vote
0answers
35 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
vote
1answer
23 views
Is grammar that describes an equation in prefix (Polish) notation always unambiguous?
I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation:
$$Expr \rightarrow + \, ...
1
vote
1answer
20 views
Defining nullable symbols and the first set of a grammar
I'm practicing for an upcoming exam and am being tripped up by a review problem. The problem gives the following grammar:
$$S \rightarrow AB\$$$
$$A \rightarrow \epsilon | a | (T)$$
$$T \rightarrow T,...
1
vote
1answer
25 views
Defining Grammar for Given Language
I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-...
1
vote
1answer
20 views
Language of particular CFG
Let:
$ G = <V, \Sigma, R, S >: \\
V = \{ S,A,B,C \} \\
\Sigma = \{0, 1\} \\
R: \\
S \to CSC|A \\
A \to 0B1|1B0 \\
B \to CB|\epsilon\\
C \to 1|0
$
I need to find the language (no need to ...
0
votes
1answer
21 views
Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$
I am trying to find a context sensitive grammar for the type-1 language
$L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$
I can construct the first part with
\begin{align*}
S &\to aSbB \mid B \...
0
votes
0answers
9 views
Writing a Grammar to a Language [duplicate]
is there a general method or approach to writing grammars to a language? I do not want to describe the language I have to write a grammar to as I do not want a specific answer. I am looking for ...
0
votes
1answer
20 views
What complexity class is this set of grammars? RE?
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$, $X \to a$, or $X \to \epsilon$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ ...
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 ...
0
votes
0answers
15 views
What complexity class does is this set of grammars? L-complete?
Given a grammar where every rule has the form $X \to Y$ or $X \to a$ and (($X \to Y$) implies ($Y \to X$)) where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$...
1
vote
1answer
42 views
What complexity class is this set of grammars?
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, ...
0
votes
1answer
38 views
What complexity class does is this set of grammars? NL-complete?
The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some ...
1
vote
1answer
48 views
Would the following grammar be ambiguous?
I have the grammar $S = aSbS|bSaS|\varepsilon$. When I was first looking at the problem I thought it was unambiguous. When I looked at the answer it said that it was ambiguous. The solution it gave ...
0
votes
1answer
38 views
Grammars and Parsing: Ambiguity in Sequences
BACKGROUND
I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches.
Given terminals:
"a": KEYWORD
"b": ...
5
votes
2answers
528 views
Complement of a DFA without final states
Let $L_1=\{Q,\Sigma,q_0,\delta,Q\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting ...
0
votes
0answers
19 views
Grammar for $\{a^n b^m c^{n+m} \mid n,m \ge 1\}$ [duplicate]
Please help me solve this problem:
Design a grammar for the language $\{ a^n b^m c^{n+m} \mid n,m\ge 1\}$.
2
votes
1answer
106 views
Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?
I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
0
votes
1answer
31 views
How can I determine the start non-terminal of a CFG?
Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (disjoint).
$A ::= x|y|z$
$B ::= a|b|c$
...
$...
-1
votes
2answers
28 views
Finding the language generated by a grammar
Forgive my lack of knowledge, I am new. I tried to find the language generated by this grammar
S → aA | bS | cS | ɛ
A → aA | bB | cS | ɛ
B → aA | bS | ɛ
And I ...
