Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
0
votes
0answers
20 views
How can I find a language from a given PDA
I have the following PDA:
And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{...
2
votes
2answers
96 views
Decidability of equivalence to existential formulas
I'm looking for an algorithm to decide 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 ...
0
votes
1answer
41 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
16 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 ...
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 ...
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
1answer
129 views
Regularity of language of words containing a square
$$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this ...
-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.
72
votes
8answers
94k views
How to prove that a language is not regular?
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
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
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 ...
0
votes
4answers
192 views
What is the language generated by a given grammar
Given the grammar
$s \to aSb \mid bSb \mid a \mid b$;
what is the language generated by the grammar over the alphabet $\{a,b\}$?
When I was solving this question I was a bit confused
about the ...
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 ...
1
vote
1answer
29 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
218 views
Context free grammar for $bin(n)bin(n+1)^R$
It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\{bin(n)bin(n+1)^R : n \geq 0\}$ is context free.
Here, at 1.b, is a PDA which ...
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 ...
1
vote
2answers
209 views
PDA to accept language with more a's than b's and c's
My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of ...
3
votes
2answers
82 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
2k views
What is the difference between formal language, regular language and regular expression? [closed]
I want to know the difference between these three languages and it would be great if you would give some examples as well.
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 ...
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 ...
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$, ...
1
vote
1answer
49 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 ...
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
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 ...
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
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.
3
votes
0answers
83 views
Generating valid sentence with respect to attribute grammar
Given a context free grammar, both the algorithm for determining whether a given string is grammatical and the algorithm for producing a grammatical string in that language are well understood. To ...
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
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$:
$\...
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 ...
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\}, $$
...
1
vote
1answer
36 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
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
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 ...
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 ...
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 ...
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}$ $\...
