Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
2answers
60 views

Prove that the language of squares is not regular using homomorphism

If a language like $L$ is regular, then any homomorphism of $L$ is regular too. So, if $h(L)$ is not regular, then we can conclude that $L$ is not regular. Assume that the language $L=\{yy:y \in ...
1
vote
1answer
40 views

What's the difference between the concatenation and union of symbols within a language

I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression (a + b)* (abba* + (ab)*ba) Can ...
1
vote
1answer
80 views

Show language is not regular

Show that the following languages are not regular in two ways: first by using closure properties then by using the Pumping lemma: $$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$ ...
3
votes
3answers
60 views

Regular expression for a binary string containing even number of 0's

To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it): The regular expression for the above according to me ...
1
vote
2answers
58 views

non LL(1) grammar but LL(1) language

I'm reading a Basics of Compiler Design and on page 84 it is making the following statement: A language may well be LL(1) even though the grammar used to describe it is not. Can someone give ...
0
votes
1answer
53 views

A recursive language minus a recursively enumerable language results in a recursive language?

I know that a recursively enumerable language minus a recursive language results in a recursively enumerable language, but I'm confused with the above question. Aren't all recursive languages also ...
2
votes
1answer
95 views

Proving that the scramble of a regular language is context-free

For strings $w$ and $t$, if they have the same length and comprise the same characters (namely, they are two permutations of these characters), then $w\sim t$. For a string $w$, define an operator ...
1
vote
1answer
55 views

context sensitive language finite or infinite

let L be a CSL. (my understanding/ memory/ expectation is) the problem is L finite or infinite? is undecidable. where was this 1st proved/ published? are there any cases in the literature of ...
0
votes
1answer
38 views

Prove using pumping free lemma for context-free languages

One of the exercises I tried to make I failed miserably. The question was as follows: Show that the language $L = \{ w \,|\, n_a(w) \cdot n_b(w) = n_c(w) \}$ is not context-free. (with $n_a(w)$ ...
4
votes
1answer
57 views

Closure properties of the class of inherently ambiguous CFLs

is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are ...
3
votes
2answers
72 views

Why are palindrome and not-palindrome both context-free?

Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two ...
0
votes
1answer
49 views

If L is a regular language then the language replace(L,σ,τ) is also regular

I am stuck at the following problem: Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular. ...
2
votes
1answer
25 views

Can a non-regular language be made regular via concatenation when they don't share characters?

So this is a follow-on question to my other question (Can we make a non-regular language regular via concatentation?). Given the following, $L = \{0^n1^m2^m \mid n>1, m>1\}$ $A = \{0^n \mid ...
4
votes
1answer
40 views

How do I show that an equivalence class of a language containing an empty string is infinite

The question is as follows: Let $L$ be a language (not necessarily regular) over an alphabet. Show that if the equivalence class containing the empty string $[ \epsilon ]$ is not $\{ \epsilon ...
4
votes
1answer
57 views

Is it decidable whether a linear language contains a square?

A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings). Question: Is it ...
7
votes
5answers
891 views

Can we make a non-regular language regular via concatentation?

My question is basically given three languages A, B and L, where L is A and B concatenated together and B is proven to be non regular, is it possible to find an A that makes L regular?
1
vote
1answer
43 views

Implementation-level description of a Turing Machine

I am new to Turing Machines! I need to work on an implementation-level description of a Turing machine that decides the language L = an where n is a Fibonacci number. I know Fibonacci numbers ...
1
vote
1answer
27 views

What is the resulting set for {0,1}*\{0}*?

If we have a language $L = \{0\}^*$ over the alphabet $\Sigma=\{0,1\}$, what is $\Sigma^*\backslash L$? That's what I think: $\{0,1\}^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... \}$ ...
-1
votes
1answer
143 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, thank you. :)
4
votes
3answers
280 views

Is the set of CFGs that contain all odd and even length words Turing-decidable?

$ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)} $ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd ...
5
votes
1answer
74 views

How did each class of languages receive their name?

If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable ...
1
vote
2answers
68 views

Is the language of strings with an integer ratio of the number of a's to the number of b's context-free?

Consider the language $L \subseteq \{a,b,c\}^*$, where $w \in L$ if and only if the ratio of the number of $a$'s in $w$ to the number of $b$'s in $w$ is an integer. I've been unable to find a ...
0
votes
0answers
20 views

What is the complement of this Context-Free Language? [duplicate]

$L = \{ a^i b^i c^i | i \ge 0 \}$ I understand that it's everything not in $L$, so every string where $\#a's = \#b's = \#c's$ is not in $L$ complement. However, I wasn't sure if strings such as $ba$ ...
3
votes
1answer
68 views

How many languages exist over a finite alphabet?

I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams. Link In "Exercises for ACS 1, Fall 2004, sheet 1", exercise 1 item C, the question ...
1
vote
1answer
48 views

Showing the the language represented by a set is regular

Is the language $L = \{ w \mid w $ is $ 3^n - 1 $ in some given representation $, n > 0 \}$ regular? I know that it is regular. If each element in $L$ is represented as decimal numbers, $L = \{ 2, ...
0
votes
1answer
36 views

Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?

I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is >= 60% of symbol A. I'm trying to think in terms of what to save on the ...
2
votes
1answer
49 views

How to pick w for the Pumping lemma if the language has no clear pattern?

I'm trying to understanding using the pumping lemma to prove that a language is not regular. I sort of understand how it works when the language describes strings with a particular form, like in this ...
0
votes
1answer
51 views

Complement of $a^n b^n c^n$

I am trying to find the complement of the language $L = \{ a^n b^n c^n \mid n \ge 0\}$. I know that one of the things I gotta do is take out $n \ge 0$ so $\{a^n b^n c^n \mid n > 0\}$ but I feel ...
-2
votes
1answer
56 views

Regular expression of a given language [closed]

Could somebody please confirm if a regular expression of language: $$ L := \{b(ab)^n a^m \mid n, m \geq 0\} $$ is $$\{b, (ab)^* a^*\}? $$ And if not, could somebody please tell me why?
0
votes
0answers
63 views

How to efficiently represent any possible mutations to a string of a given length?

I'm trying to find a "language" or a way to express any change that has occurred to a string. I'm given two strings; a seed string and a new string of the same length that came from it. I'm trying to ...
0
votes
2answers
54 views

Showing that a language satisfies the pumping lemma

I am wanting to show that this language fails to show that it is not context-free. So, in essence, it satisfies the pumping lemma If L = {ambncndn | m,n >= 1 } Should I have n be the constant of the ...
0
votes
0answers
12 views

Proof by pumping lemma [duplicate]

I'm trying to use the pumping lemma proof to show that the following language is context-free rather than regular {ba^n bc^n | n ≥ 1} I've been looking at tutorials on Youtube to try and gain ...
0
votes
1answer
40 views

Need to remove indirect left recursion from CFG

I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$ In the ...
1
vote
1answer
31 views

How do I get and/or verify a formal Grammar for a given formal Language? [duplicate]

I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language. After some trying and fiddling I found one that I ...
-1
votes
1answer
66 views

Need to give a CFG for this language?

I have the language: $$ L = \{0^m1^n \mid 0 ≤ m ≤ n\text{ or }0 ≤ n ≤ 2m\}. $$ My goal is to give an equivalent context-free grammar for this language, but I am unsure if I am going about it the ...
0
votes
1answer
39 views

If a language is context free, then its complement is decidable

I am having a bit of trouble figuring this out. If L is context-free then we know it is decidable. The class of decidable languages is closed under complement thus, $L$ $\cap$ $L^{c}$, therefore ...
-1
votes
1answer
74 views

Converting a language to a PDA?

I am trying to convert the follow language $$L = \{0^m1^n \ | \ 0 \le m \le n \le 2m\}$$ We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though ...
1
vote
3answers
48 views

Misconception in taking Pumping Length of language {a} to be $2$

I would like to know why the pumping length of language {a} is $2$ as said in this chat discussion. Eventhough this discussion proves trivially that the pumping length of language {a} is $2$ I ...
2
votes
2answers
57 views

Proving a CFG is ambiguous?

I have a CFG: S --> 0S1S | 1S0S | ε I'm trying to prove that it is ambiguous, but the steps to proving so are confusing me. So if I pick a string, let's say ...
0
votes
1answer
43 views

How can I prove that a Regular Language is closed under Union given two languages with different alphabets?

I need some help to prove that a Regular Language is closed under the union, using a DFA with two differents alphabets.
3
votes
1answer
90 views

Non-regularity of the set of primes in unary encoding using Myhill-Nerode

I have found many proofs for this using pumping lemma, I'm curious of how to proof it via Myhill-Nerode theorem. Suppose $L= \{a^p \mid p \text{ is prime}\}$ is regular. Then we have congruence such ...
-2
votes
2answers
153 views

How is $a^nb^nc^{2n}$ not a context free language, where as $a^nb^mc^{n+m}$ is? [duplicate]

$L_1 = \{a^mb^nc^{m+n}: n,m>1\}$ I know $L_1$ is CFL and works with a pushdown automata. $L_2 = \{a^nb^nc^{2n}: n>1\}$ The language $L_2$ should also be a CFL because it looks similar, but ...
0
votes
0answers
22 views

How do I prove a language is regular? [duplicate]

I've done a lot of research on this topic, but still don't feel very confident about it. Let's say the example is: For a language L over an Σ, define N(L)={w∈Σ∗: wk∈L for some k∈Σ∗}. Prove that, if L ...
1
vote
1answer
84 views

Regular and Non-Regular Language

My friends and I are taking a formal languages class and for one of our homework questions we have to prove if these languages are regular: 1) L = {apaqi : p and q are fixed integer values, i >= 0} ...
0
votes
1answer
28 views

Writing context free grammar

I have the following language: {0m1n0n1m | m,n ≠ 0} I was wanting to write Context-free grammar for it. I'm a little confused because the rule doesn't mention that m and n are not equal to each ...
0
votes
1answer
19 views

Does preparing min DFA by combining equivalent states always result in min DFA

I know the following fact: If $Ma_N=\{w:n_a (w)=Nk,k≥0\}$, then Number of states in $$Ma_{N1}×Ma_{N2} =Ma_{N1}∪Ma_{N2} =Ma_{N1}∩Ma_{N2} =Ma_{N1}-Ma_{N2} =LCM(N1,N2)$$ where $n_a (w)$ is the ...
-1
votes
1answer
78 views

Confusion in Pumping Lemma

I would like to know whether we could pump $ba$ into $bbba$ where x=$b$,y=a,z=$\epsilon$ using the finite state machine given in the image 1. For example as given in this image 2 where the string ...
-2
votes
1answer
65 views

Context sensitive grammar for an odd number of copies of the same word

Let $L = \{ w^m \mid m = 2k +1, k \ge 1 \}$. Please give some idea to write a Context sensitive grammar for $L$. Will it be like $L' = \{www \mid w \in \{a, b\}^*$? Then for each $w$ we have to ...
3
votes
1answer
63 views

If L is regular, so is L2 (proof using closure properties)

I've got a question that asks me to explain how if a language L is regular, then so is: $M=\{s \in \{a, b\}^* |\ \exists\ t \in L\ such\ that\ |s|_a = |t|_a\}$ I believe I would have to get M into ...
5
votes
1answer
54 views

What can be said in general about a homomorphism between two regular languages?

In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can ...