The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
38 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
19 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
40 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
18 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
51 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
103 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
22 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
35 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
27 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
82 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
73 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
22 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
103 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 ...
0
votes
0answers
36 views

Smallest grammar problem on a single character.

Let the alphabet be $\Sigma = \{a\}$. Say $s = a^6 = aaa aaa$. If the repeated variable $A = aa$ appears $k$ times in the expanded starting rule of a smallest grammar $G_s$ for $s$. Then that ...
1
vote
1answer
55 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
0answers
28 views

Algebra on trees?

Given a forest of trees, I am interested in tree recombination operations that produce me a sub-forest spanned by some selected trees. To me, it somehow resembles space and spanned subspace in ...
0
votes
0answers
27 views

Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
0
votes
1answer
33 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
158 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
41 views

Chomsky Normal Form for Integer Recognition

If I have the following CFG, which is just the regex [0-9]+: ...
1
vote
1answer
39 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
78 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
160 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
358 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 ...
0
votes
1answer
65 views

Palindromes with 2 symbols and $3|l(u)$

The following grammar generates palindromes with 2 symbols. $$G=\{\{S\}, \{a,b\}, \{S\rightarrow\epsilon|a|b|aa|bb|aSa|bSb\}, S\}$$ So if I'm right, each $u$ in the language $L$ generated by $G$ is a ...
0
votes
1answer
29 views

How can I show ithat a language is regular?

I have a very quick question about regular languages, I think $\{a^{2n}| n\geq 1\}$ is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ...
0
votes
1answer
39 views

Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
0
votes
1answer
34 views

How to notate truth conditional functions

My semantics professor uses functions to teach her class. She wrote the following sentence and three examples in one of her slides. [[smile]] is a function that takes something, let’s call it x, and ...
0
votes
1answer
62 views

Creating a Push Down Automaton from a Grammar

I have the following grammar, but I'm not sure what exactly it is that it does: $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p ...
1
vote
1answer
315 views

Eliminating Epsilon Production for Left Recursion Elimination

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any I have the following grammer ...
1
vote
1answer
91 views

Context free grammar for a language

I have this context free language $L = \{x^{3i} y^j z^k\ |\ i \ge 0 \land k \gt 2j \gt 0\}$ I'm working out a ...
0
votes
1answer
69 views

Shortest word possible

In a give context-free grammar language $L = \{z^{3x} y^i w^j \ |\ x \ge 0 \land j \gt 2i \gt 0\}$ The shortest possible word that does not belong to the ...
2
votes
1answer
222 views

Converting Context Free Grammar to Chomsky Normal Form

This is an exercise that I had to complete in my class and I struggled a lot with it $$\begin{align*} &S\to 0A0\mid 1B1\mid BB\\ &A\to C\\ &B\to S\mid A\\ &C\to S\mid\epsilon ...
1
vote
1answer
82 views

Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
1
vote
1answer
44 views

Consider this grammar

Consider this grammar: \begin{array}{l} S \to aabBba \mid aAb \mid aab \\ bBb \to bCa \mid aaa\\ aA \to aC \mid bba\\ C \to aab \mid Cb \end{array} This is clearly context-sensitive (CS). It's not ...
0
votes
1answer
129 views

Help with context sensitive grammar [closed]

I am not able to understand writing a context sensitive grammar for this language. Can anyone please help me out? $L = \{ a^p | p \text{ is a non-prime integer}\}$
1
vote
1answer
188 views

Write a grammar that generates the strings over {a,b} starting with a

The answer is: S -> aA, A -> aA, A -> bA, A -> a, A -> b, S -> a Any idea how they got this?
1
vote
1answer
1k views

Build regular grammar from regular expression

Is there an algorithm for creating a regular grammar directly from a regular expression? All the discussions and notes I found so far go through an intermediary step of creating an FA for the reg ex ...
2
votes
1answer
64 views

NFA from grammar productions

Based on this grammar: \begin{align} G = (\{S,A,B\}, \{a,b, c\}, S, P) \end{align} \begin{matrix} \\P: \\S → abaS | cA \\A → bA | cB | aa \\B → bB | cA | bb \end{matrix} I created this NFA: ...
0
votes
1answer
197 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^*(ba)^*bb$ My solution, it seems a little too short like I'm ...
1
vote
1answer
53 views

NFA from regular expression

I'm trying to make an NFA from the following regular expression. I'm not sure about the edges between nodes $q2$ and $q4$, maybe someone can point out where everything went wrong.
0
votes
1answer
30 views

Language made by a regular expression

I created a language from this regular expression but I'm not sure about it, especially where I wanted to use the $w$ to express a sequence of terminals. The expression: $r = a a ^{*} (b + bb + bbb) ...
1
vote
1answer
26 views

Regular expression for a language

I made a regular expression to match this language but I'm not sure it's right. Perhaps someone can show me where it deviates. The language: $L = {a^{n} c b^{m} (cc)^{p} : n \geq 1, m \leq 1, p\geq ...
0
votes
2answers
73 views

Constructing regular grammar

I'm trying to make a regular grammar for this language: $$ L = \{ a^ncb^m(cc)^p : n\ge 1, m\le 1, p\ge 0\} $$ Where the alphabet is $ \Sigma = \{a,b,c\}$ It seemed like right-linear. This may be ...
1
vote
0answers
26 views

What do you call a mildly-context sensitive grammar in which the LHS must appear in the grammar spec?

For instance: $$ S \rightarrow aAbAb \\ aAb \rightarrow AAa \\ A \rightarrow Aa | a $$ $aAb$ is alright to have on the left-hand side since it occurs directly in the grammar spec. Further indirectly ...
0
votes
1answer
161 views

Understanding how to convert a PDA to a CFG

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions: (current state, stack head, input character, replacement for old stack head, ...
0
votes
1answer
206 views

Formal grammar for the language $L = \{w\in\{a,b\}^*,\,w=xx,\,x=a^nb^na^mb^m,\,n\ge0,\,m\ge0\}$

What is the grammar of this language? $$L = \{w\in\{a,b\}^*,\,w=xx,\,x=a^nb^na^mb^m,\,n\ge0,\,m\ge0\}$$ For example: $abab$, $abaabbabaabb$
3
votes
2answers
85 views

Are there any trivial examples of languages that cannot be produced by formal grammars?

Since the cardinality of the set of all languages that can be produced by a grammar is smaller (countably infinite) than the cardinality of the set of all languages (which is uncountable infinite) I'm ...
0
votes
1answer
15 views

What is the name of a variable $v\in V$ in a grammar $G=(V,T,P,S)$ s.t $v\Longrightarrow_{G}^{*}\epsilon$?

I have a variable $v\in V$ in a grammar $G=(V,T,P,S)$ s.t $$v\Longrightarrow_{G}^{*}\epsilon$$ Where $\epsilon$ is the empty string. Is there a name for such a variable $v$ ?