# Tagged Questions

48 views

### Finding the CFG (Context Free Grammar) of a language

Can we write a CFG (Context Free Grammar) for the set of all non-empty string whose length are multiple of 3 on the alphabet $\Sigma = \{A,R,G,C\}$
35 views

14 views

### Z Spec - How to constrain X Y Coordinates

I'm trying to build a system state schema in Z spec that specifies the following: Points of interest use (X,Y) coordinates to specify their location. a small point of interest exists that only has 1 ...
98 views

### Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings

This is an exercise from Introduction to Languages and the Theory of Computation, by John Martin. Suppose $L$ is a language over $\Sigma$, and $x_1, x_2, ... , x_n$ are strings that are pairwise ...
45 views

### Is L Regular language

Prove whether language $a^{(13)^n}$ is regular, or not. Please, provide the most formal answer as it could be. My teacher is very strict. Thanks in advance.
68 views

### How can a formal language $L$ concatenated with itself $L^k$ ever equal $L^{k+1}$

I’m seeking an explanation of how any formal language L concatenated with itself $k$ times, $L^k$, can equal that same language concatenated with itself $k+1$ times, $L^{k+1}$. The problem I’m ...
285 views

### Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
113 views

### Push Down Automata which has 2 stacks

I am doing homework in Formal Languages. I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA. Thanks!
208 views

### Logical Conjunction of Binary Decision Diagrams

Compute a Binary Decision Diagram for $B1∧B2$. Furthermore, for an arbitrary BDD B you can use the equations $B∧F=F$, $F∧B=F$, $B∧T=B$ and $T∧B=B$. To construct the BDD i start from the leaves ...
121 views

### Homorphism and Context Free Grammar

Could you explain me concept of homomorphisms and usage of it to the following problem which requires to prove that $L$ is not context-free? $$L=\{ba^{n-1}ba^nb:n\ge 1\}$$ Thanks
46 views

### Pumping lemma and CFG

I am solving problem in pumping lemma for context-free languages. I want to ask a hint for the following problem $$L=\big\{www:w\in\{a,b\}^*\big\}$$ Thanks
74 views

### Pumping lemma for CFG

it is another my question. Can you give me hint to solve the following problem? Prove that $L=\left\{a^{n^2}:n\ge 0\right\}$ is not a context-free language? Thanks!
46 views

217 views

### Recursively enumerable languages are closed under the min(L) operation?

Define $\min(L)$, an operation over a language, as follows: $$min(L) = \{ w \mid \nexists x \in L, y \in \Sigma^+ , w=xy \}$$ In words: all strings in language L that don't have a proper prefix in ...
156 views

### Given a Turing Machine T, create another Turing machine T2 such that L(T) $\neq$ L(T2)

Consider an algorithm that accepts a Turing Machine M and constructs another Turing machine M2, such that L(M) $\neq$ L(M2). Show that such algorithm cannot exist. My answer: If such algorithm ...
110 views

### Formal language homework problem - extend(L)

This is my attempt to solve an exercise from a formal languagues class. Consider the following definition: extend(L) = { w $\in$ $\Sigma^*$ | $\exists$ x $\in$ L, y$\in$ $\Sigma^*$ . w = xy ...
208 views

### Determining if a language is Recursively Enumerable

Here is a problem from John Hopcroft's "Introduction to Automata Theory" that I'm having a hard time trying to understand. Exercise 9.2.5: Let L be recursively enumerable and let Overscript[L, ...
121 views

### How to prove that $L=\{w \mid \#a(w)=\#b(w)=\#c(w)\}$ is not context free using closure

How can I prove that the language $L = \{w \mid \#a(w)=\#b(w)=\#c(w)\}$ is not context free using closure? EDIT : I know that the language $L_1 = \{a^i b^i c^i \mid i\geq 0\}$ is not a context ...
1k views

### Determine if a Turing Machine M, on input w, will move its head to the left, at least once

Here is a problem from my formal languages class Consider the following problem: Determine if a Turing Machine M, on input w, will move its head to the left, at least once. ...
123 views

### Pumping lemma for regular “pumped formal language”

Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. We define $$\verb+lmult+(L)=\left\{x^iu\;|\;x\in\Sigma,u\in\Sigma^*,i>0,xu\in L\right\}\cup\{\epsilon\}.$$ [...] Show the ...
255 views

### Proving Grammar Correctness

I'm having difficulties in proving the correctness of grammars. The following problem and my pity attempt to solve it show that I may not understand even the basics of such proofs. Very ...
204 views

### Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false

Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata) The above hint did not help me :(
352 views

### Algorithm to tell whether a regular language contains at least n strings

I'm taking a course on formal languages and was given this exercise: Give an algorithm to tell whether a regular language $L$ contains at least $100$ strings. Can someone give me a hint? Thanks! ...
69 views

### Prove that L($G^R$) = $(L(G))^R$

I'm stuck with this exercise from a course in formal languages that I am taking. Could someone help me with this? Big thanks! For any w, define $w^R$ as $\lambda ^R \text{ =$\lambda $}$ ...
202 views

### Regular Expressions - Over the alphabet $(a, b, c)$

Express the language of all words whose first letter, if it exists, is the same as its last letter over the alphabet $(a, b, c)$. This is what I have so far: ...
231 views

### Need help in formal grammar for the $L = \{wcw : w \in \{a,b\}^\ast\}$

I can't create formal grammar for the language like $wcw$ where $w$ is the word in $\{a,b\}^\ast$ and $c$ is just a letter Thanks!
Given a formal language L, is $L \subset L^*$ or is $L \subseteq L^*$? To give context, I am tasked with proving whether or not there exists a language such that $(L^*)^c = (L^c)^*$. Assuming the ...
I have this problem that I can't seem to be able to wrap my head around, and I was wondering if there was someone here that could help me understand it. Let $L_1$ be a regular language over \$\{a, b, ...