Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
0
votes
1answer
37 views
Let u and v be two strings. What about the reverse order of their concatenaited string?
let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$?
Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.
1
vote
1answer
14 views
Converting CFG from GNF to CNF
I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is ...
5
votes
4answers
2k views
Is the infinite language unrecognizable in a Turing machine?
This question is building up on an older one, here.
But now let's say we keep $Σ=\{0,1\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable?
That means 1, 11, 11111, 1111111, and so on ...
2
votes
2answers
83 views
Decidability of equivalence to existential formulas
I'm looking for an algorithm to recognise if a given first order formula over a fixed vocabulary admits a logically equivalent existential one (i.e. a formula in prenex form where all quantifiers are ...
1
vote
1answer
30 views
Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b [duplicate]
How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$?
I'm sorry I can't give any approach of what ...
2
votes
2answers
39 views
Is the reverse of a closed under operation maintainable?
I'm looking at the following question from this handout:
The class of decidable languages is closed under union
My question is, does this hold in reverse? Is there a phrase for this?
Basically, if ...
0
votes
1answer
44 views
DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$
$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$
Any idea? I have problem with this kind of task.
-1
votes
1answer
44 views
How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
I don't have any idea. Can someone help me.
1
vote
1answer
28 views
Pumping Lemma vs Myhill-Nerode [duplicate]
I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much.
Let us take the following as an example:
$$ L = \{ a^n b^n \mid n \ge 0\} $$
...
0
votes
0answers
26 views
Show that the language L = {www : w ∈ {0, 1} ∗} is not regular [duplicate]
Hey was wondering if I'm applying the pumping lemma correctly for this proof or if this proof could be improved?
Suppose $L = \{www:w\in\{0,1\}^*\}$ is a regular language. Let $p$ be the number from ...
1
vote
1answer
26 views
Pumping Lemma on Language with subtracted length
My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given
$$ L = \{ a^k b a^{m-...
0
votes
0answers
12 views
How to find equivalence classes for a regular language? [duplicate]
I was wondering if there is a formal approach to find equivalence classes for a regular language.
My guess:
Construct a minimal DFA based on given regular language.
Based on states in DFA, we can ...
1
vote
1answer
64 views
Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?
$ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $
I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My ...
0
votes
1answer
85 views
Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's
The following question on the theory of computation is GATE 2019 CS question 24:
For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid
x = a^{2+3k} \text{ or } x = b^{10+12k}, k ...
3
votes
2answers
81 views
How to prove the equivalence of two CFG for balanced parentheses?
Given two CFGs for balanced parentheses.
$S \rightarrow SS \mid (S) \mid \epsilon$
$S \rightarrow S(S)S \mid \epsilon$
How do I show that they are equivalent?
I have been able to show $ L(2) \...
1
vote
1answer
38 views
What is the signature of a formal language?
I will briefly state the context where my doubts arise.
I know the following definitions.
A formal language is a set of well-formed formulas. It's a tuple constituited by an alphabet and a formal ...
1
vote
1answer
23 views
Is there any problem that is R-complete and RE-complete
R-complete, i.e. it is an analogue to all recursive language can be reduced to that problem and also recursive? Or is there a really such definition?
RE-complete is described on wikipedia. But what ...
1
vote
1answer
25 views
$A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$
I'm trying to exhibit two formal languages $A,B ⊆ \{0,1\}^*$ such that $A^* = B^*$ and $\{0,1\}$ is contained in $A$ but not in $B$.
Finding a language for $A$ is very easy, but I get stuck on $B$, ...
0
votes
1answer
48 views
Proving that A(B ∩ C) ⊆ AB ∩ AC
A(B ∩ C) = { UV | U ∈ A, V ∈ B and V ∈ C } for the left part.
ΑΒ = { UV | U ∈ A, V ∈ B },
ΑC = { UV | U ∈ A, V ∈ c },
AB ∩ AC = { UV | U ∈ AB and AC, V ∈ AB and AC } for the right part.
How can I ...
2
votes
1answer
35 views
How to use homomophism in closure proofs?
I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, ...
1
vote
1answer
48 views
How I can find all equivalence classes by Myhill-Nerode?
first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest.
The topic is Myhill-Nerode ...
1
vote
1answer
26 views
Prefix/suffix property of language containing only empty word
Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?
The definition says that language has prefix/suffix property requires that there is no code word in the ...
4
votes
1answer
53 views
Is there a recommended process for designing CSGs (other than intuition)?
I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the ...
0
votes
1answer
36 views
operate infinite times over a regular language
Let $T:Σ^*\to Σ^*$ be an operation such that $T(L)$ is regular for all regular languages $L \in Σ^*$.
Is it possible to prove $T^∞(L)$ is regular?
$T^∞(L)=\bigcup_{i=1}^{\infty}{T^{i}\left(L\right)}$...
0
votes
0answers
13 views
Difference between grammar productions and derivations
My understanding is that a production is a 'rule' of a grammar which defines how a symbol sequence can be rewritten into another symbol sequence.
A derivation on the other hand is the process of ...
0
votes
1answer
39 views
Allowing an empty (epsilon) transition in a PDA
I'm trying to allow an empty transition in a PDA for the following language:
Alphabet: $Σ = \{a, b, c\}$
Language: $L = \{ a^ib^j \mid i \neq j \} \cdot \{ c \}^\ast$
Examples of words in $L$:
$\...
2
votes
2answers
41 views
Is this counting language context free?
Let $\Sigma = \left\{ 0,\,1,\,2\right\}$. I want to look at the following language: $L=\left\{ xyz \, | \, |x|_0 + |z|_0 = |x|_2 +|z|_2 \wedge y \in \left\{ 1 \right\} ^{*} \right\}$.
I would like ...
2
votes
1answer
25 views
Proving a LL(1) equivalent grammar doesn't exist
Consider the following CFG
$S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS$
How can we prove formally that an equivalent $LL(1)$ grammar does not exist. I feel that intuitively an equivalent $LL(1)$ ...
2
votes
2answers
43 views
Myhill-Nerode equivalence classes of $\{1^n0^n\}$
I have the following task and its solution.
Question
Given the language
$$ A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\}, $$
...
0
votes
0answers
28 views
Formal language representation of program
I have numerous records, composed of words. Each word gets translated into vectors, with a variable number of channels, provided that that word exists in a specific lookup dictionary.
For n number of ...
-2
votes
1answer
42 views
Provide “regular” grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$} [duplicate]
I'm trying to understand the approach to constructing an grammar which accepts the language
${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$ }
Thanks.
1
vote
2answers
44 views
Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n
The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the ...
1
vote
1answer
35 views
How to build a finite automaton for right quotient of a regular language?
Let $L$ be a regular language over $\Sigma=\{a,b,c\}$. Build a finite automaton for $L/\{a\}$.
Because $L$ is regular then a DFA exists for it: $A=(\Sigma, Q, q_0, F, \delta)$.
Let $M$ be a finite ...
1
vote
1answer
38 views
Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?
Let $L$ be a regular language over alphabet $\Sigma$. $L$ is the result of merging $2$ languages letter by letter that is for $a_1a_2...a_n\in L_1, b_1b_2...b_n\in L_2, L=a_1b_1a_2b_2...a_nb_n$. $\...
0
votes
1answer
41 views
Constructing a PDA with an unequal number of a/b
I'm looking at this pdf for problems: http://www.public.asu.edu/~ccolbou/src/355hw5solf10.pdf
I found question 3g to construct a pushdown automata for the following:
{$ {a^i b^j}$ | ${i \neq j}$}
...
1
vote
1answer
32 views
How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?
Prove that if $L$ is regular over $\Sigma=\{0,1,2\}$ then the following language over $\{0,1,2,\$\}$ is also regular:
$$
G=\{\$x\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } ...
1
vote
1answer
35 views
How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
I think this could be a good exercise and the conditions are ...
1
vote
1answer
45 views
Grammar of words with exactly $k$ prefixes in another grammar
Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that
$$ L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\} $$
where $\text{Pref}(w)$ is the set ...
0
votes
0answers
19 views
What is “Phrase structure grammar”?
I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar:
Type-0 grammars generate recursively enumerable languages. The
...
0
votes
1answer
29 views
Does left factoring CFG make it unambiguous?
I came across following problem:
If the CFG is left factored then it must be Unambiguous and Not left Recursive.
TRUE/FALSE?
I have many thoughts about this. But I feel they are somewhat ...
1
vote
1answer
37 views
REC and RE under intersection
Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither?
Assume $L_{3}$ is the intersection of some language $L_{1}$ $\...
2
votes
3answers
58 views
how can i say a given problem is in co-NP using it's definition?
I seem to be having trouble understanding the connection between the formal definition of co-NP and how problems are concluded to be in it. co-NP is defined to be the class containing the languages ...
2
votes
1answer
31 views
How to choose a word to apply the Pumping Lemma?
I have some questions about the PUMPING LEMMA.
First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes.
And sorry about my English :)
...
0
votes
1answer
38 views
Chomsky Classification of Languages
Given is a language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ ; where $N^{+}$ are the natural numbers excluding 0.
I have found a type-1 grammar to describe it:
$S \to A_1A_2$
$A_1 \...
1
vote
1answer
57 views
Induction on strings (words)
Given is an alphabet $\Sigma = \{ 0, 1, 2 \}$ and a function quer to calculate the cross sum of a word.
$quer : \Sigma^*\to \Bbb N$ with:
$$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\
...
2
votes
0answers
37 views
If there is comparison between two variables then language is not regular. Then how the below two languages L1 and L2 Regular? Please Explain [duplicate]
How these two languages be regular.If there is comparison between m and n since (n < m) is the condition to be satisfied.
1
vote
0answers
30 views
How to create model for a powerful language whose programs are guaranteed to terminate?
I'm creating a powerful regular expression matching system that can be augmented by adding small microprograms to deterministic finite automaton (DFA) states. The microprogram solves the big bang ...
1
vote
3answers
74 views
Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2
Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$
whereas $|w|_a$ is the number $a$'s in ...
0
votes
1answer
22 views
How to generate a grammer from this language? [duplicate]
I'm trying to generate a grammar from this language:
L={a^i b^j c^k d^l : i+j=k+l}
to be clear its a in the power of i and b in the power of j... and so on, so ...
2
votes
1answer
50 views
How to prove a language is not regular using the Pumping Lemma?
I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult.
Task:
Prove that $M = \left\{ a^...
