Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

-1
votes
1answer
136 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
274 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
72 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
19 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
66 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
34 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
48 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
47 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
52 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
36 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
65 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
36 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
67 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
47 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
52 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
37 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
88 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
138 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
63 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
52 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 ...
2
votes
1answer
56 views

Find the number of words in a language of given length

I was asked the following question: Consider the language $S^*$, where $S = \{ab, ba\}$, write out all the words that have seven or fewer letters? How do I go about calculating the number of ...
7
votes
5answers
618 views

Is there a known method for constructing a grammar given a finite set of finite strings?

From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around? If given n strings of m length, it should be possible ...
3
votes
1answer
60 views

Is the Kleene star of an intersection contained in the intersection of Kleene stars?

I need to find if given two formal languages $L_1$ and $L_2$ $$(L_1 \cap L_2)^*\subseteq (L_1^* \cap L_2^*) $$ I think that it's true since this can be rewritten as $$ \bigcup^\infty_{i=0}(L_1 \cap ...
1
vote
1answer
48 views

Regular languages and constructing a regular grammar

I'm pretty new to computer science and just read about the concept of grammars. Now, I have a practical problem to solve. Here is the alphabet {a, b, c, d}. How ...
3
votes
1answer
77 views

Index of a language and its reversal [duplicate]

The index of a language is the number of Myhill-Nerode classes that it has. It is also equal to the number of states in the minimal DFA for the language. What is an example of a language that has a ...
10
votes
3answers
2k views

Is there any uncountable Turing decidable language?

There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
1
vote
3answers
81 views

Regular Expression simplification

Does $(0 + 10^{*}1)^{*}$ simplify to the following language: Set of all binary strings with even number of ones. In specific, does the * inside the brackets get evaluated first or the outer * gets ...
-2
votes
1answer
49 views

Proving that a programming language is not regular

I am wanting to show that the C programming language is not a regular language. The alphabet would be ASCII characters and comments, strings, char can contain arbitrary characters. Would I best ...
4
votes
1answer
74 views

Proving that English is not a regular language

I am wanting to try and prove that the English language is not regular. The alphabet is the set of all words in the English dictionary. Looking at sentences, I was able to use this pattern of ...
0
votes
2answers
31 views

Transform grammar for repeating characters into LL(1)

I have the following simple production rule: S -> Sa | a Which is left-recursive, and can recognize strings such as a or aa, etc I tried to make it right-recursive, but I cannot find a way ...
1
vote
1answer
39 views

regular expression to accept all strings other than one containing ads or adlib [closed]

My intention is to select only those packages whose name do not contain adlib or ads. But if i add *adlib* and *ads* it selects all packages containing the ...
0
votes
1answer
195 views

Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

Suppose we define an operation such that $$A \text{ avoiding } B = \{w \in A \mid w\text{ has no substring in }B\}\,.$$ How can I prove that, if $A$ and $B$ are regular then $A\text{ avoiding }B$ ...
1
vote
1answer
61 views

Decidable languages [duplicate]

A recursive (decidable) language is defined as a language for which there exists an algorithm deciding if a string is or not in the language that terminates for every possible input. The question ...
12
votes
3answers
1k views

Finding examples of languages that are “anti-palindromic”

Let $\Sigma = \{ 0, 1 \}$. A language $L \subseteq \Sigma^* $ is said to have the "anti-palindrome" property if for every string $w$ that is a palindrome, $w\notin L$. In addition, for every string ...
1
vote
1answer
53 views

Ambiguity Problem (Language Structures)

I'm having serious issues fining an unambiguous version of a particular grammar. I've looked online for help for this particular problem and for general methods for finding unambiguous versions of ...
0
votes
2answers
99 views

How would a DFA be designed to accept a language defined as the string comprised of every other character in each string in another language? [duplicate]

For example, you have a DFA that accepts the language comprised of strings aabbbaa and aaabbbbaaa, and you want to create a new DFA that accepts a language comprised of strings abba and aabba (strings ...
2
votes
1answer
32 views

CFG for words that are not a concatenation of the same word [duplicate]

I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language: $ L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ...
0
votes
2answers
197 views

How do you find an infinite regular language that is a subset of a non-regular language?

In order to do this, we would probably need the non-regular language to be infinite as well, then find some definition for the non-regular language in order to fulfill the requirement, but I don't ...