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
18 views

Grammar for $\{a^ib^jc^{i+j}\ |\ 0\le i<j\}$

I've just finished FLA exam and there was one task I wasn't able solve. I was supposed to find context-sensitive grammar for $\{a^ib^jc^{i+j}\ |\ 0\le i<j\}$. Well, I didn't (I found only 0-type ...
0
votes
1answer
9 views

Find a Context-Free Grammar for this Context-Free Language

$$ L = \{w_1w_2 : w_1, w_2\, \in \, \{a,b\}^*, w_1 \ne w_2\} $$ So far I have produced this grammar which will produce a string of odd length which follows that $w_1$ and $w_2$ wouldn't be equal. $$ S ...
1
vote
0answers
8 views

Every LL Grammar is not ambigious

An LL grammar is a formal grammar that can be parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser ...
0
votes
0answers
25 views

NFA Correctness

Hello I have the following instructions: L3 is all strings where (i) the number of $b$'s is twice the number of $a$'s, and (ii) each substring with three occurrences of $a$ and $b$ should contain ...
0
votes
1answer
15 views

Find the language of a given grammar

I have the following grammar: S ⇒ Aa A ⇒ B B ⇒ Aa I need to find the language of this grammar but I am having trouble. I have never had to make a language out of a grammar that has no end state so ...
0
votes
0answers
15 views

Constructing a grammar for language of all squared words

I need help in constructing a grammar for this language: $L = \{ \alpha \in \{a\}^* \mid \alpha = a^{n^2}, n \in \mathbb{N}_0\}$ All I can tell about $L$ is that it should be at least context-free. ...
1
vote
1answer
29 views

A grammar for the complement of language $L=\{a^{t+3}b^t:t \ge 0\}$

Assume that the language $L=\{a^{t+3}b^t:t \ge 0\}$ is given. Q1 : How can we write a grammar for the complement of this language? Q2 : Assume that $L'=\{a^nb^m:n\ge0,m\gt n\}$ is given. Can you ...
1
vote
0answers
32 views

Is there a concept of distance between number of steps needed to move from one step to another?

Let's say that we have a set of rewrite rules: $$AB \mapsto AC, A \mapsto B, B \mapsto A$$ Given the two strings $ABC$ and $BCC$ we know we can rewrite $$ABC \mapsto ACC \mapsto BCC$$ We can ...
0
votes
1answer
29 views

Identifying a regular language

I'm currently trying to answer a question were I have to confirm if a language is regular or not. If the language is not regular I have to give an informal answer to why the language is not regular ...
1
vote
1answer
30 views

Using a language to define a grammar

I'm currently having trouble understanding how to use a language to generate a grammar. Using the language: $$L=\{a^n b^m | n, m \geq 1\}$$ as an example: I know (from my notes) that this ...
1
vote
2answers
51 views

Using Pumping Lemma to prove a language not regular

I'm currently stuck on a problem were I'm asked to look at a language and prove whether or not it is a regular language or something else such as context-free. I've been given the example: $$\{...
2
votes
0answers
24 views

How do I get and/or verify a formal Grammar for a given formal Language?

I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language. After some trying and fiddling I found one that I ...
4
votes
1answer
38 views

Identify recursive languages?

Consider the following languages. $L_1 = \{<M> \mid M \text{ takes at least 2016 steps on some input}\}$, $L_2 = \{<M> \mid M \text{ takes at least 2016 steps on all inputs}\}$ and $...
0
votes
1answer
21 views

What is flaw on my proof to identify any string of $L_2$ using single stack?

Consider the following languages: $L_1=\{a^nb^mc^{n+m}:m,n≥1\}$ $L_2=\{a^nb^nc^{2n}:n≥1\}$ Which one of the following is TRUE? Both $L_1$ and $L_2$ are context-free. $L_1$ is context-free while ...
1
vote
1answer
32 views

Which grammar generates the language: $L = \{a^i b^j d^k | i, j, k ≥ 0 ∧ j < k\}$

I am unsure, how can the second answer be the right one - and why not the first one? Can some one explain it step by step? Why i think the first answer is right: $aS \to aSA \to aAAd \to abddd$
1
vote
1answer
26 views

How to identify context free language?

Consider the following context-free grammars$:$ $G_1: S → aS|B, B → b|bB$ $G_2: S → aA|bB, A → aA|B|ε, B → bB|ε$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$, ...
0
votes
0answers
33 views

Queue automaton algorithm for accepting primes

What is an example of a queue automaton algorithm that accepts prime numbers, encoded as strings of prime length? For example, if the input is either of ...
0
votes
0answers
12 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
44 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
41 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
10 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 expression....
1
vote
1answer
61 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 E+E|E*...
1
vote
1answer
41 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
17 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
20 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
33 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
42 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
35 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
35 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
48 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
15 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
117 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
172 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
29 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 ...
0
votes
1answer
74 views

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

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
68 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 → aS_2b+...
1
vote
1answer
27 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
17 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
97 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
85 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 ...
1
vote
1answer
49 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 ...
1
vote
1answer
66 views

Wrong proposition in “Atiyah and Macdonald”s book?!

In page 6 of "Introduction to commutative algebra" write that: $a \cap b = ab$ provided $a + b = (1)$ But I think it's not true, by considering $a = b = (2) \in \mathbb Z_6$
7
votes
3answers
150 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
52 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
50 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
95 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
35 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
57 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
125 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, ...