In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) is a set of production rules for strings in a formal language. A formal grammar is a set of rules for rewriting strings, along with a "start symbol" from which rewriting starts. Therefore, ...

learn more… | top users | synonyms

0
votes
0answers
10 views

Indirect Left recursion.

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...
0
votes
1answer
39 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
1
vote
2answers
39 views

When can we do induction over the language defined by a formal grammar?

We can define the grammar of propositional calculus as $G=(\{S\},V_T,D,S)$ where $V_T=\{(,),\land,\lor,\Rightarrow,\Leftrightarrow,\lnot\}\cup\mathcal{P}$. $\mathcal{P}$ is the set of propositional ...
0
votes
0answers
8 views

Make a translation scheme which removes unnecessary brackets

I have ariphmetic expressions which contain $+$, $*$ and brackets. I need to make a translation scheme which can be combined with syntax analysis and which removes unnecessary brackets from ...
1
vote
1answer
38 views

Prove that two arithmetic grammars generate the same language

In my university's automata theory book it is claimed that the following two arithmetic grammars generate the same arithmetic language but no proof is shown. $G_1=(\{E\}, \{a,+,*,(,)\}, \{E\to ...
1
vote
1answer
39 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
1
vote
1answer
16 views

There are substrings that are never cut by a smallest grammar.

Define a substring of a string $s$ to be compressible if $|E| = 2$ and the number of non-overlapping occurences $\#_s E$ of $E$ in $s$ is $\geq 3$, or $|E|\gt 2$ and $\#_s E \geq 2$. E.g. $s = a^6 ...
1
vote
0answers
19 views

Chomsky Normal Form Transformation

I've been struggling a bit with creating the Chomsky normal form derivation of a grammar that I have been given The grammar in question is: $S \to BB \mid 0A0 \mid 1B1 \\ A \to C \\ B \to S \mid ...
0
votes
1answer
32 views

How to write this sentence formally

I have this sentence Prediction is a numerical value, $P_{a,j}$, expressing the predicted likeliness of item $i_{j} \notin I_{u_{a}}$ for the active user $u_a$. This predicted value is within the ...
0
votes
2answers
30 views

What is the language of following CFG?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. $$S → aS \mid A \\ A → aAb \mid bAa \mid \epsilon$$ Which of the following ...
0
votes
0answers
25 views

Formal definition of an array or vector

First of all, excuse me if I compare arrays and vectors erroneously, I'm not mathematician. I need to know how to define formally an array of length n and composed by ones and zeros depending on ...
1
vote
2answers
28 views

Proving L(G) = L using induction and deriving a schema

Consider the following grammar G: S -> aS -> aTb -> a T -> aTb -> a How would I prove that ...
0
votes
0answers
31 views

Converting CNF to GNF

Considering the CNF grammar below, I need to convert it to GNF using the equations in a semiring method and Order the equations in the the natural order. However, I Do not have to convert the ...
0
votes
1answer
14 views

Are these two grammars similar?

Language is L = {a^nb^m | n.m >=1} Grammar 1 : S->AB B -> bB|b A-> aA|a Grammar 2 : ...
1
vote
1answer
76 views

How to draw DPDA for language $L = \{a^ncb^{2n} | n \geq1\}$over the alphabet $\Sigma =\{a,b,c\} ?$

An exercise problem $:$ Give a deterministic PDA for the language $L = \{a^ncb^{2n} | n \geq1\}$over the alphabet $\Sigma =\{a,b,c\}$.Specify the acceptance state. My attempt $:$ Grammar of given ...
-1
votes
1answer
13 views

Newbie Question formal languages N-1 for a language typ 3

I have the following problem: If I have a Grammar G with (Vn, Vt, P, S) Vn ={S}, Vt = {0} P: S -> 0S S -> 0 Why is the derivation from G: 0^(n-1)S? S => 0S => 00S => ... => 0^(n-1)S => 0^n Is it ...
0
votes
0answers
104 views

Construct DFA from context-free grammar

What is simplest and shortest way to build minimal DFA from context-free grammar (equivalent to regular grammar)? For example, the grammar: A ::= aB B ::= {b} ...
0
votes
1answer
22 views

Construct a Grammar for a language that includes mod

I am trying to construct a regular grammar for the following language: $$L = \{ w \ | \ (na(w) - nb(w))\mod3!= 1 \}.$$ I'm struggling to understand what it is this language produces, and thus ...
-1
votes
1answer
50 views

Better approach to solve this problem?

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production (i.e., of type $A \rightarrow \epsilon$ and $A \rightarrow a$) to ...
0
votes
1answer
63 views

CFG for the language $L = \{(a^n)(b^m)(c^k) \mid k = |n – m|, n,m,k \geqslant 0\}$

These two are among given solution. I find (A) is correct, but the answer shows (D). Please answer which one of this is correct and why/explain. (A) $S → S_1S_3$, $S_1 → aS_1c + S_2+ λ$, $S_2 → ...
1
vote
1answer
26 views

Inquiry into operator precedence grammar

I have come accross something called operator precedence grammar https://en.wikipedia.org/wiki/Operator-precedence_grammar and I would like to know about the specific mathematical properties is ...
0
votes
0answers
16 views

Do bracketed L-systems impose any restriction on the rules' right-hand sides?

In order for an L-system to meet the definition, do brackets need to be balanced at all? Either at the resulting derivation, or at the rule level?
2
votes
0answers
91 views

Of strings and substrings: A problem of probability

Problem Let $\Sigma=\{a, b\}$. Let $\Sigma^*$ denote the Kleene star of $\Sigma$: \begin{equation*} \Sigma^* = \{\varepsilon, a, b, aa, ab, ba, bb, aaa, aab, \ldots\} \end{equation*} where ...
0
votes
1answer
78 views

Construct grammar $\ a^i b^j c^{i+j} b^j a^i $

I've been going through old exams at my college and I found this problem that I haven't yet been able to solve. Construct grammar defined on the alphabet $\ \{{a, b, c}\} $ which generates strings of ...
0
votes
1answer
43 views

Context-free language or not

It is language: $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$ Is it context-free or not? I have two versions: 1)Pumping lemma(refute): get a word $uvxyz = aabcd$ if $i=2$ we get ...
7
votes
3answers
127 views

Formal writing in math: equations

What is the formally correct way to solve a bunch of equations in math? Is it \begin{align} 42x = 4324 \\ x = 4324/42 \end{align} or \begin{align} 42x = 4324 \\ \Rightarrow x = 4324/42 \end{align} or ...
2
votes
1answer
44 views

Is this language context-free or not?

I have a problem to solve, the problem is: Is the language of strings $$L=\{0^x1^y:x\nmid y\}$$ context free? I suspect it isn't, I spent some time trying to make a grammar that could ...
1
vote
1answer
47 views

Write grammar for given language

I'm trying to write a grammar for the language below: $$(a+b)^*−\{𝑤𝑤𝑤 ∶ 𝑤\in\{a,b\}^*\}$$ could anyone help me?
3
votes
0answers
79 views

How to show $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is ambiguous?

I'm recently familiar with this site and prefer to ask a very hard problem :) How can we prove that the following language is inherently ambiguous? $$L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m ...
3
votes
1answer
31 views

Context free grammar and regular expressions

Consider a grammar $G = (V, \Sigma, R, S)$ where $V = \{S\}$, $\Sigma =\{A, B\}$ and $R$ has two production rules, namely $S \to S^+ AS $ and $S \to B$. Is $G$ context-free? The $^+$ symbol is Kleene ...
1
vote
1answer
55 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
2
votes
1answer
120 views

Languages and their relation : help

This is not a homework question though, this is something I wish to know to add to my own knowledge. While reading one of the texts on automata (K.L.P. Mishra, "Theory of Computer Science : Automata, ...
-1
votes
1answer
56 views

$L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$ [closed]

Why the following is not context free? Anyone could describe it for me. $L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$
0
votes
1answer
122 views

Context Free Grammar and some details [closed]

Why this grammar shows a Context Free and Linear Language, (i.e, not context sensitive or non-context free). S -> SBA | a BA -> AB aA -> aaB B -> b
0
votes
1answer
98 views

Eliminating epsilon-productions in grammar

I am wondering how to eliminate epsilon-productions in grammar: S → S0 S → 1 S → AB B → AC A → ε C → ε I know that because of ...
5
votes
1answer
42 views

Formal Grammar generating $0^p$

Exercise: Find the formal grammar generating the language ${0^p}$ in the binary alphabet for $p$ prime. I have absolutely no clue where to start, nothing of the 'usual' construction strategies seem ...
0
votes
1answer
136 views

Construct a grammar that generates this language

This is a homework problem. The problem is: Find a grammar that generates this language: L = {w: |w| mod 3 ≠ |w| mod 2} over alphabet Σ = {a}. The transitions I came up with are: S -> Baa B -> ...
1
vote
2answers
306 views

Find a grammar that generates this palindrome language

This is a homework problem. The problem is: Find a grammar that generates this language: L = {wcw^R: w ∈ {a,b}+ } over alphabet Σ = {a, b, c}. I have tried many different transitions, but can't ...
0
votes
1answer
433 views

Determine type of grammar?

Let $V = \{S, A,B, a, b\}$ and $T = \{a,b\}$. Determine whether $G = (V, T, S, P)$ is a type $0$ grammar but not a type $1$ grammar, a type $1$ grammar but not a type $2$ grammar, or a type $2$ ...
0
votes
1answer
23 views

Given the following grammars with start symbol $\langle S \rangle$, specify the type ($0$, $1$, $2$ or $3$)

So I'm working on this problem set and I'm having some trouble figuring out what type each one of these are. I think (a) is type $0$ and really can't tell for (b). I know the difference between each ...
0
votes
1answer
138 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
1
vote
1answer
60 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
0
votes
1answer
38 views

Predictability of a grammar

I've encountered this in a book: The language $ \{ a^n0b^n \mid n ≥ 1\} ∪ \{a^n1b^{2n} \mid n ≥ 1\}$has no predictive grammar. (A predictable grammar is that in which no two rules of production for ...
1
vote
1answer
432 views

Context free grammar $L=\{a^ib^jc^k|j=i+k-2\}$

$L=\{a^ib^jc^k|j=i+k-2\}$ This expression surprise me a lot and put me into deep thinking. what i am doing by solving the expressions: ...
1
vote
0answers
32 views

What about generlizing grammars?

Say we came up with a finite grammar (specifies a finite number of strings) given a set of input strings. How then do we generalize the grammar so that it works for larger input strings and also ...
0
votes
1answer
59 views

Chomsky Normal Form for Integer Recognition

If I have the following CFG, which is just the regex [0-9]+: ...
1
vote
1answer
40 views

There is a sequence of operations on grammars of a string that strictly decreases the size of grammars down to the smallest grammer.

I'm trying to figure out the smallest grammar problem, which yes I know is impossible since it's such a hard problem, but humor me for a sec. Let $g$ be a smallest grammar for the string $s$ over the ...
3
votes
1answer
80 views

Why use *λx.x* instead of *f(x)*?

In my semantics class, we're learning about using (abusing?) lambda calculus. So far the professor hasn't imparted any reason for using λx.x instead of using f(x). Why use lambdas instead of basic ...
2
votes
1answer
326 views

Is well formed XML context-sensitive grammar?

Solution Copy language is noncontracting, so it's context-sensitive. Look at https://en.wikipedia.org/wiki/Noncontracting_grammar for transforming noncontracting grammar to explicitly $\alpha ...
4
votes
3answers
372 views

How to denote this in game theoretic notation

I'm writing a paper that demonstrates that linguists can use the concepts in game theory to infer what interlocutors naturally infer when the literal meaning of their utterances doesn't ostensibly ...