Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
0answers
6 views

FOIL system for learning PROLOG rules from facts

I'm trying to use FOIL, a system from the 1990s developed by Ross Quinlan, to learn Prolog rules from facts. However, the input file syntax is tricky for me. Could someone provide me an example input ...
1
vote
2answers
9 views

Two regular languages over the same alphabet, regular or not regular?

TRUE or FALSE: Let $L_1, L_2$ be any two regular languages over the same alphabet $\Sigma$, then the language $L=\{w\in\Sigma^* \mid w\in L_1 \text{ or } w\notin L_2\}$ is regular. So we have to ...
0
votes
0answers
10 views

Proving a language is context free without closure rules or grammar?

I know how to prove a language is context free through closure rules and through providing a grammar. However, in my exercises I've come across a language not suitable for either: $L = \{uc^nv\ \ |\ \...
1
vote
1answer
16 views

Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?

I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars. However, I've encountered this statement from my notes: With $\epsilon$ productions in the ...
1
vote
1answer
26 views

Proving that a language satisfies the pumping lemma condition

I have to proof that $L = \{ a^{2i} b^{2j} \mid i,j \in \mathbb{N} \}$ is a regular language, and how it meets the Pumping Lemma condition. For the PL, there is a string $xyz \in L$ such that $y \neq ...
0
votes
0answers
13 views

Cut word from regular language into two parts and swap them. Is the language still regular? [duplicate]

Define language $L’$ for given regular language $L$ as: $$L’=\{uv | u,v\in\Sigma^{*}, vu\in L\}$$ is language $L’$ also regular? Hello, I need some help with solving this question. I need somehow to ...
0
votes
2answers
31 views

How to prove this language is context free?

There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free. $L = \{a^{(n+1)} b^{(...
1
vote
1answer
14 views

Unambiguous grammars with different right and left hand derevations

I read recently that for an unambiguous grammar the left hand derevation need not necessarily be equal to the right hand derevation. Can someone give an example of this.
0
votes
0answers
26 views

Is there a pda with maximum 3 state for every CFL?

This is the first question I'm asking here I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?
2
votes
1answer
124 views

What is the relation between parsing languages and checking languages?

I have looked at a number of textbooks on computability theory. They typically have the following form: Define a language class (regular, context-free, context-sensitive, recursively enumerable) ...
0
votes
0answers
15 views

How can I create the context free grammar for this language? [duplicate]

I need help finding the context-free grammar for this language. $$ L = \{a^ib^jc^k \in \{a,b,c\}^* \mid \text{$i,j,k \geq 1$, and $i=j$ or $i=k$ or both}\}. $$ I've found a way to satisfy $i = j$ ...
0
votes
0answers
22 views

how to write a language for context-free grammar generates the empty string?

How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
1
vote
1answer
29 views

How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?

This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3. $$ \text {Let }b_i \text{ denote } i \text{...
2
votes
1answer
57 views

Formal Languages: if $L_1^* = L_2^*$, then $L_1 = L_2$

The question is: For all languages $L_1$ and $L_2$ , if $L_1^* = L_2^*$, then $L_1 = L_2$. We know that two languages are equivalent if $L(G_1) = L(G_2)$, where $L(G) = \{w \in T^* \mid S\Rightarrow^*...
-1
votes
1answer
32 views

Can an infinite regular language be decomposed in this way?

If $A$ is an infinite regular language, can there exist a finite regular language $B$ such that $A = BB^*$?
4
votes
2answers
830 views

If L is not regular and is a proper subset of L1, does it follow that L1 is not regular?

If $L$ is not regular and $ L \subset L_1$, does it follow that $L_1$ is not regular also? Can you please provide an explanation? Thanks in advance.
0
votes
0answers
41 views

Prove that regular languages are closed under Kleene star [duplicate]

Given $L$ is a regular language, how can I prove that $L^*$ is a regular language too? I've constructed an NFA which contains a new initial state that has an $\epsilon$-transition to the original ...
-1
votes
1answer
24 views

What is the language generated by this grammar?

I'm struggling to find the language generated by the following grammar: Any help would be appreciated.
0
votes
0answers
11 views

How to write regular expression [duplicate]

The set of all strings over {0,1} such that every block of 4 consecutive symbol contain at least two 0's Can you guys tell me what is the correct answer for this ?
0
votes
1answer
50 views

Are there more languages than functions?

My gut says "no", but I don't know why. For any function $f$ over strings on an alphabet, one can define a language in which every word is just the concatenation of a string $s$, a delimiter, and $f(...
1
vote
1answer
32 views

Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable

I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma_1$ is Turing recognizable. I'm not sure what's the general way to approach this, but I noticed $A_{TM}$ is in $\Sigma_1$ ...
1
vote
2answers
59 views

Prove the following language is regular?

Assume $L_1$ is a regular language, and define: $$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$ Show that $L$ is regular. I first tried to prove by showing ...
0
votes
1answer
19 views

EVEN-CFL Decidable / Undecidable - Rice-Theorem

Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$ Question : Is EVEN-CFL ...
4
votes
0answers
53 views

Reference on relating Post systems to string rewriting systems and formal grammars?

wikipedia states: Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...] It has been proved that any Post canonical system is reducible to such a ...
0
votes
2answers
43 views

Formal grammar with constraints on the number of each symbol

I have a language where each type of symbol is only allowed a particular number of times, but the order isn't important. For example, lets say there are three symbols $a, b, c$, and a valid string in ...
0
votes
1answer
24 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
0
votes
0answers
36 views

NFA-$\epsilon$ extended transition function for inverted strings

It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows: \begin{align*} \hat\delta: Q &\times \Sigma^* \rightarrow \mathbb{P}(Q) \\ \hat\delta(q,\epsilon) ...
1
vote
3answers
127 views

Large DFA to regex?

For an assignment for one of my courses, one of the questions is to provide a regular expression for the language: "the set of strings such that the number of 0’s is divisible by six, and the number ...
0
votes
0answers
15 views

Proof that $L = \{w | na(w) + nb(w) = nc(w)}\ is not regular [duplicate]

So.. my professor mentioned that it has something to do with $Wi = a^5b^i$ $Zij = c^(i+5)$ which is in the language But then mentioned that $Wj = a^5b^j$ $Zij = c^(i+5)$ Is not in the language, ...
1
vote
1answer
32 views

Do closure properties for languages go the other way?

For example I know the union of 2 either decidable or recognizable languages is decidable or recognizable. But say the union of two languages is decidable, does this tell us anything about themselves?
0
votes
1answer
33 views

Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e

An example from Sipser's book, Introduction to the Theory of Computation, shows that it is not decidable for a $TM$ to recognize whether a $CFG$ (or a type 2 grammar) generates $\Sigma^*$, where $\...
0
votes
0answers
28 views

One-way-function based on Friedberg numberings

A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 Levin showed an example of a function which is one-way if there are one-way functions. As far as I know, it ...
2
votes
1answer
106 views

Prove {<M> | TM M on input 3 at some point writes symbol “3” on the third cell of its tape} is recursively enumerable but not recursive

Question: Let $$S = \{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape} \}.$$ Show that $S$ is r.e. (Turing acceptable) but not recursive ...
0
votes
0answers
31 views

Handling left recursion without left factoring with stateful parser combinators

Consider the language of simple types $$ T \mapsto B \ \mid\ T \rightarrow T \\ B \mapsto \text{Bool} \ \mid\ \text{Int} $$ where $\mapsto$ stands for productions to avoid ambiguity with the ...
0
votes
1answer
28 views

How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s. Also, I have a hint HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
4
votes
1answer
87 views

Prove or disprove {wtw^R | |w| = |t|} is context free

The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$ It looks like the language can be "pumped" by context free pumping lemma, ...
0
votes
1answer
38 views

CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$

Given the language: $$ L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \} $$ I propose the following grammar: $$ \begin{align*} S &\to \varepsilon \mid aSbS \mid bSaS \\ S &\to ...
1
vote
2answers
251 views

There exists an algorithm to find grammar of complement of a function?

I'm wondering if there exists an algorithm to solve the following problem: Given a grammar $S$ of a context-free language $\mathcal{L}$, find a grammar $S'$ such as $L(S) = L(S')^c $. I note ...
1
vote
1answer
72 views

Using MyHill Nerode theorem to prove a language is non-regular

The language is $S = (a^nb^m | n \geq m)$. I'm having trouble understanding MyHill Nerode theorem. Basically if I want to use MyHill Nerode theorem to prove $S$ is non-regular, I have to show that ...
1
vote
1answer
36 views

Proving the regularity of the following language

I have a question about the following problem: Prove that the language $\{a^nva^n | v \in \Sigma^*, n \ge 1\}$ is regular over $\Sigma = \{a,b\}.$ I know that in proving a language is regular I ...
1
vote
2answers
80 views

Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?

I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using ...
-1
votes
1answer
38 views

Set-theoretic difference of two languages in CFL - REG

Let $L_1,L_2\in$ CFL $-$ REG, with $L_1\subset L_2$. Which of the following always holds? $L_1-L_2\in$ CFL $-$ REG and $L_1-L_2\in$ REG. $L_1-L_2\in$ REG and $L_2-L_1\in$ CFL $-$ REG. $L_1-L_2\in$ ...
1
vote
1answer
45 views

Use the pumping lemma to show it's not regular

I just learned pumping lemma this week and got confused on this question. B={$a^{fn}$ | $f_n$ is a Fibonacci number} for $a \in Σ$. Hint: the sequence of Fibonacci numbers get increasingly further ...
0
votes
1answer
23 views

Equivalent regular grammar with minimum number of nonterminals

Given a set of terminal symbols $\Sigma=\{a,b\}$ and a set of nonterminal symbols $N=\{S,A,B\}$ with start symbol $S$, then the two following sets of production rules are equivalent: $S\to aA$ $A\to ...
3
votes
2answers
165 views

If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?

I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack. But, a link of Show that { ...
-1
votes
1answer
58 views

Is a language regular if a word is in a regular language but the reverse is not?

$$A_1 = \{ x \mid x \in A , x^R \not\in B\}$$ $A$ and $B$ are regular over $\Sigma$. Is $A_1$ regular?
1
vote
1answer
45 views

Algorithm to replicate human noising of names by creating a categorical distribution given a character, with higher probabilities on similar chars

I’m trying to find a way without just hard coding to create a categorical distribution over all characters given a character but with similar looking ones having higher probability. For example, if ...
1
vote
1answer
47 views

Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

I'm trying to proof that the following language is not regular using pumping lemma. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$ I started by stating that: $|w\bar{w}| =...
1
vote
1answer
64 views

How could one prove that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ? Using induction

I am currently working on ways to prove this and got stuck proving it with induction. Any tips? How could i prove that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ?
1
vote
3answers
84 views

Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular

I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me? This was an exam question from previous year. I looked your ...

1
2 3 4 5
45