Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
0answers
5 views

modeling for asset value by Automata

I want to model asset value and their relation ship.I model one asset's value like this: state A : when asset value decrease one unit state B: when asset value increase one unit my problem is to ...
0
votes
1answer
36 views

If the strings of a language can be enumerated in lexicographic order, is it recursive?

If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?
1
vote
1answer
35 views

Show that language generated by grammar is regular

We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t $ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $ How can I show that ...
7
votes
2answers
998 views

Will $L = \{a^* b^*\}$ be classified as a regular language?

Will $L = \{a^* b^*\}$ be classified as a regular language? I am confused because I know that $L = \{a^n b^n\}$ is not regular. What difference does the kleene star make?
0
votes
3answers
74 views

What is the language generated by a given grammar

Given the grammar $s \to aSb \mid bSb \mid a \mid b$; what is the language generated by the grammar over the alphabet $\{a,b\}$? When I was solving this question I was a bit confused about ...
1
vote
1answer
13 views

What is the complement of the language with all ucv with u ≠ v?

If $L = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 \neq w_2\}$ what is the complement of language L? one of my friend said that it is $\overline{L} = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 = w_2\}$ and he ...
1
vote
2answers
39 views

Can a regular language have uncountably many strings?

Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0* as an example.) But can a RL have uncountably many strings? I'm leaning toward ...
3
votes
1answer
23 views

Is there an example of a recursive language which is not context sensitive?

I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for ...
0
votes
2answers
27 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
59 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
24 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
27 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
54 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
43 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
49 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 ...
0
votes
0answers
4 views

Is there a name to the search syntax that google uses [migrated]

Google has a standard search syntax e.g. quotations marks (") for a phrase, a prefix such "-" for qualified terms or the use of Or between words instead of and. Sounds like it is a standard with a ...
-3
votes
1answer
46 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
74 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
62 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
32 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
61 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
49 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
45 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
15 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
32 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
25 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
57 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
37 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
70 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
57 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
53 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
48 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 ...
-1
votes
0answers
11 views

non-deterministic automaton [duplicate]

I am a linguistics and I start to read some books about NLP.I have need help to solve this question. Design a non-deterministic automaton and regular expression over the alphabet {a, b, c} that accept ...
2
votes
1answer
84 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
49 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
30 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)$ ...
0
votes
2answers
28 views

Formal method - how to prevent deletion in an array

i have created a very basic model of an array list in the b method as shown below ...
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
66 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
48 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 ...
-1
votes
0answers
10 views

How do I represent the set of strings of odd length in regular expression form over the alphabet Σ = {a, b} [duplicate]

I know that a{aa}* would give you all of the odd length strings for a, but the fact that there are two elements in the alphabet are throwing me off a bit.
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
55 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
889 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
40 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
134 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
273 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 ...