-1
votes
1answer
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\} $
1
vote
1answer
35 views

Constructing PDA for a language

I want to prove or disprove that for a given two PDA's (Pushdown Automata) $M_1$ and $M_2$, we can build a PDA $M$ such that $$L(M) = \{w \in L(M_1) \mid w\text{ contains some string in ...
1
vote
0answers
49 views

If $P=NP$, prove that $L' \in NP$

I think I'm overthinking this problem and need some hints in the right direction. The goal of this question is to show that if $P=NP$ then for every language $L \in NP$ via a polynomial time verifier ...
0
votes
0answers
19 views

(L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
2
votes
0answers
62 views

Determine the language that corresponds to the following automata.

I want to determine that language that corresponds to the following automata Note: $q_{6}$ have arrow to $a$ to himself. I started with the minimal words: $aaabb$ $aaba$ $aaaba$ $bababa$ the ...
1
vote
1answer
54 views

Prove $L$ = $\{\langle M \rangle$ | $M$ is a TM over $\{0,1\}$ and $\langle M \rangle \langle M \rangle \notin \mathcal{L}(M)\}$ is undecidable.

Was stuck on this for a bit so I need to know if I am on the right track. To show that $L$ is undecidable we will show that $\overline{L}$ is undecidable instead. Suppose $\overline{L}$ is decidable ...
2
votes
0answers
73 views

Prove that $\overline{L}$ is not recognizable by showing that $B_{TM} \le_m L$

$\textbf{Problem}:$ $L$ = $\{\langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ such that for some $x \in \{0,1\}^*$, $M$ does not halt on input $x\}$. $B_{TM}$ = $\{ \langle M \rangle$ | ...
3
votes
0answers
115 views

Proving a language is not recognizable

I have the following question that I just want to verify I have done correctly. Let $L$, $L_1$, $L_2$ $\subseteq \Sigma^*$ such that $L = L_1 \cup L_2$, and $L_2$ is decidable. Prove that if $L$ is ...
1
vote
2answers
20 views

A question about operations on languages.

I come across this problem on a book. It states that: for languages A and B, $(A\cup B)^* = (A^*B^*)^*$. I know that the definition of star closure is $\left(\bigcup^{\infty}_{i=1}\right)A^i$. But so ...
1
vote
1answer
86 views

If $L_1 \cap L_2$ is decidable, prove/disprove that $L_1$ and/or $L_2$ are decidable

Question: Let $L_1$ and $L_2$ be languages over the alphabet $\Sigma$. If $L_1 \cap L_2$ is decidable, then $L_1$ is decidable or $L_2$ is decidable (or they both are). Definition of a decidable ...
0
votes
2answers
316 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
-1
votes
1answer
42 views

Finding the wrong regular expression

Which one of the following regular expressions does not define the language of all strings that ends with a. $(a + b)^*a$ $b^*aa^*(bb^*aa^*)^*$ $[a(ba)^* + b(ab)^*](a + b)^*a$ $(b + aa^*b)^*a(a + ...
0
votes
3answers
21 views

If $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$.

I am using the pumping lemma to prove a language is not regular, and would like to assert what I have stated in the title of the question to complete my proof. That is, if $s \geq 3$, $3$ divides $s$, ...
0
votes
0answers
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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.
5
votes
2answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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!
1
vote
1answer
203 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 ...
0
votes
1answer
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
0
votes
1answer
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
0
votes
1answer
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!
-1
votes
1answer
45 views

CFG and closure properties

I am solving one problem and I urgently need a hint to solve one problem: Use closure under union to show that the following language is context-free $$\left\{a^mb^nc^pd^q : n=q,\ \text{or}\;\ ...
2
votes
1answer
52 views

Formal Languages: Trouble understanding powers

I've run into an argument with some peers about how to perform power operations on languages. Say: A = {2,00} At first myself and ...
2
votes
1answer
90 views

Showing this language is not decidable by rice theorem or reduction

Consider this language: L = {<M1,M2> : M1 and M2 are TMs and L(M1) contained in L(M2) contained in {1}*} Intuition says that it's undecidable, though can ...
1
vote
1answer
166 views

Prove that if $ L $ is a regular language over the alphabet $ Z = \{ 0,1 \} $, then $ L' = \{ax \mid x \in L \} $ is also regular for any a in $Z$.

Prove that if $L$ is a regular language over the alphabet $Z = \{0,1\}$, then $L' = \{ax \mid x \in L\}$ is also regular for any $a \in Z$. I'm not sure how to even begin on this one. If even a ...
3
votes
1answer
117 views

Proving a language is not a CFL although it can be pumped

Let $L=\{a^mb^nc^k\mid k\le \min(m,n)\}$ $L$ can be pumped with the pumping lemma for Context Free Languages which makes it very difficult to prove it is not a Context Free Language. Any idea how to ...
1
vote
1answer
84 views

Finding an appropriate value to contradict the pumping lemma.

I am trying to prove that $L=${$a^mb^n | n=m^2$} is not a CFL with the help of the pumping lemma for CFL's. I chose $w=a^mb^{m^2}$ = $a^{m-S}a^Sb^Tb^{m^2-T}$ $\in L$ And now in order to contradict ...
1
vote
1answer
150 views

Decide if a formal language is a Context-free language

Let $L_1$ be a regular language. Let $L_2$ be a Context-free language. Let $L = \{w \in L_1 \mid w = \alpha_1\phi_1\alpha_2\phi_2\ldots\alpha_n\phi_n : \alpha_1\alpha_2\ldots\alpha_n\in L_2$ ; ...
0
votes
1answer
77 views

L is a context free language over {0, 1}, prove, disprove:

cont... L is a context free language over {0, 1}, prove, disprove: L1 is a CFL over {a, b}, where L1 is the language of all words from L, that 0 is converted to a and 1 is converted to bba. Thanks ...
2
votes
0answers
279 views

Regular, Context-free, Recursive, Recursively Enumerable Language Relationships

I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable. If I am given ...
3
votes
3answers
805 views

Write a Context Free Grammar for L = {x#y | x =/= reverse of y}

$x,y$ are in $\{0,1\}*$ So for example 10101#11111 is in the language, but 000111#111000 is not. This just baffles me. ...
2
votes
1answer
286 views

Confirm that this language is context free?

$$\{a^i b^j c^k \mid i\ne j\text{ or }j\ne k\}$$ Is this language context free? I believe it is based on the following CFG but I would like some confirmation that I'm right. $$\begin{align*} ...
5
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
2answers
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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. ...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
1
vote
2answers
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 :(
1
vote
1answer
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! ...
1
vote
1answer
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 $}$ ...
0
votes
1answer
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: ...
1
vote
1answer
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!
2
votes
1answer
210 views

Kleene closure over a formal language

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 ...
0
votes
2answers
104 views

What (formal) language does this describe? And, how do I prove it's regular?

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, ...
1
vote
1answer
146 views

What exactly is “formal language theory”?

In studying combinatorics, I learn about "Formal Language Theory". So is there any interesting concrete application of this theory in mathematics, say for example combinatorics? (I confess, I google ...