Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
2answers
33 views

Is the given language finite or infinite?

I have an idea regarding whether this language is finite or not, but for some reason I am still having some issues regarding exactly grasping what makes a language finite or infinite. I know that ...
0
votes
2answers
72 views

If L is a regular language, how to prove that L' is also regular?

I've been trying to construct a proof of the following statement the whole day but I got stuck: If $L$ is a regular language, the language $L_{}{'}$ consisting of all words in $L$ containing the ...
0
votes
0answers
30 views

Is the language of all DFAs that accept the empty language regular?

Is $E_{DFA}$ in the class of regular languages? $\qquad E_{DFA} = \{ \langle D \rangle \mid D \text{ is a DFA }, L(D) = \emptyset\}$ My argument is that it is because all of the DFAs in $E_{DFA}$ ...
0
votes
1answer
35 views

Convert C language code to problem specification by computing the invariant of a program

Suppose that you need to give a problem specification of some problem P and you have an implementation of P, in C. I have 2 questions: Can you obtain the formal specification of the problem if you ...
1
vote
2answers
58 views

Show that a language cannot be generated by linear grammar

I have a language $ L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$ that is a language with even number of b's. I found a grammar for it with these rules: $S \rightarrow aS \ | \ bL \ | \ \lambda $...
3
votes
2answers
50 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
-3
votes
1answer
52 views

Prove that TM does not decide this language

So my problem is how can I show that this TM does not decides this language. $$L = \{a^nb^nc^n\ |\ n \geq 0\} $$ It might be a basic problem and seem silly to you but still I do not know how to ...
-3
votes
1answer
50 views

Finding the language generated for CFG

What language generated by the following context-free grammar 1) S------> SaS | b i already know the answer to question one but to prove it would is be something like this: S -----> SaaS -----> baab ...
6
votes
1answer
82 views

Why do we study closure properties of formal languages?

In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is ...
1
vote
3answers
90 views

Is there a non-recursive and uncountable language L?

Does there exist a non-recursive language, L, such that the cardinality of L is uncountable? I would really like an explanation as to why this question is true or false because at the moment, I have ...
0
votes
2answers
33 views

Probabilities, Unigram and Bigram [closed]

Assume that we have these bigram and unigram data:( Note: not a real data) bigram: #a(start with a) =21 bc= 42 cf= 32 de= 64 e#= 23 unigram: # 43 a= 84 b=123 c=142 f=161 d=150 e=170 ...
-4
votes
2answers
106 views

odd length palindrome's f=language [closed]

Find the language generated by the following grammar over the input alphabet = {a,b}. S –> aSa | bSb | a | b The language generated by the above grammar over the alphabet {a,b} is the set of (A) ...
2
votes
1answer
52 views

Recursively enumerable but non recursive subset of an infinte recursive language

How can we show that, for every infinite recursive language, it has a subset that is recursively enumerable but not recursive? I think we need to show there's a list of natural numbers that can't be ...
0
votes
1answer
47 views

representing set of non-overlaping string in formal notation

I want to represent a set of any substrings which come from an original string with constraint that all substrings should not be overlapped. To be more clear please consider the example below: e.g. <...
0
votes
0answers
16 views

An example of a very hard decidable language [duplicate]

What is an example of a language, which is very hard to compute though still decidable (and preferably "simple" in terms of understandability)? The language should provably not be in $NP$, and, other ...
0
votes
0answers
42 views

Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...
0
votes
1answer
33 views

Is the union of a non-regular and a regular language regular?

I am studying Automata and stuck in a question that says: Is the following a regular set {a^p, where p is prime} U {even-length strings}? As we see here this language consists of two sub-languages. ...
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 \{0,...
1
vote
1answer
42 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
83 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}$$ $$\text{...
3
votes
3answers
61 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
63 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
60 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
116 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
62 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
42 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
58 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 answered?...
3
votes
2answers
76 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
51 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
893 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
44 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
28 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, ... \}$ $\{0\}^*...
-1
votes
1answer
153 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
281 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
69 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 is,...
1
vote
1answer
50 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
41 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
51 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
54 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
14 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
44 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 ...