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

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 ...
9 views

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 ...
38 views

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 ...
17 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 : ...
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 ...
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 ...
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} ...
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 ...
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 ...
68 views

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 ...
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 ...
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$
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 ...
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 ...
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?
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 ...
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 ...