# Tagged Questions

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, ...

24 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 ...
9 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 ...
14 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. ...
28 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 ...
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 ...
24 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 ...
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 ...
44 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: ...
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 ...
30 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 ...
18 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 ...
30 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$
25 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$, ...
30 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 ...
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 ...
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 ...
40 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 ...
9 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 ...
60 views

19 views

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 ...
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?
96 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 ...
81 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 ...
48 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 ...
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$
140 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 ...
50 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 ...
49 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?
87 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 ...
33 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 ...
56 views

125 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
127 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 ...