Tagged Questions
0
votes
0answers
22 views
CYK algorithm and CNF
Why do we need CNF to be able to apply CYK algorithm? Because it operates on two symbols on table or other reason?
1
vote
1answer
34 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
123 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
0answers
15 views
Precedence Relation Table and Bottom-Up parsing
I have following rules:
E->E+T|T
T->T*P|P
P->(E)|V
I need to create a precedence relation table. It is said that it can be accomplished Wirth-Weber ...
0
votes
0answers
27 views
Weak Precedence Grammar and Bottom-up parsing
I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation?
Any ...
0
votes
1answer
38 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
37 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
45 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!
0
votes
1answer
24 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
44 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
63 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
87 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
97 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
68 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
126 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
67 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
165 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
368 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
156 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*}
...
4
votes
1answer
155 views
Recursively enumerable languages are closed under the min(L) operation?
Define $\min(L)$, an operation over a language, as follows:
$$ min(L) = \{ w | \nexists x \in L, y \in \Sigma^+ , w=xy \} $$
In words: all strings in language L that don't have a proper prefix in L
...
0
votes
1answer
138 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
94 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
113 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
78 views
How to prove that $L=\{w|\#a(w)=\#b(w)=\#c(w)\}$ is not context free using closure
How can I prove that the language $L=\{w|\#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 | i\geq 0\}$ is not a context free ...
1
vote
1answer
599 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
96 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
148 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
118 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
188 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
61 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
152 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
159 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
141 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
93 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, ...
0
votes
1answer
119 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 ...
2
votes
2answers
151 views
Is it possible to prove that $L$ is a regular language?
Let $L = \{a^{f(m)} | m \geq 1 \}$ where $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ is monotonically increasing and complies that for all $n \in \mathbb{Z}^+$ there is $m \in \mathbb{Z}^+$ such that ...
