Stack Exchange Network

Stack Exchange network consists of 175 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

2
votes
1answer
150 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 ...
1
vote
1answer
40 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
55 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
49 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
53 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
47 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
58 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
35 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
18 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
76 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
150 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
118 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
45 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
24 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
30 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
54 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
39 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, ...
2
votes
1answer
110 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
38 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
54 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
40 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
17 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 ...
1
vote
1answer
62 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
44 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
31 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
62 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
30 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
48 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
54 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
54 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
45 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
115 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
36 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
39 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
48 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
22 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
43 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
40 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
64 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
54 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
57 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
60 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
52 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
32 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
81 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
24 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
79 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^...
1
vote
1answer
52 views

RAM BSS model based (or its variant) computer recognizing Boolean languages

Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or ...
0
votes
2answers
36 views

Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?

My book states that the language $$L_1 = \{a^nb^n\mid n\geq 1\}$$ is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really ...
0
votes
0answers
14 views

What are some differences between regex (FSM) in computer science with regex in programming? [duplicate]

Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.? I would like to know some ...