Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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}$ $\...