Regular Language – Context Free Language

I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question

Let $ A$ be a $ regular$ $ language$ and $ B$ be a $ CFL$ over the alphabet $ \sum^*$ , which of the following about the langauge $ R=\overline{A}-B$   is  $ TRUE?$

a. $ R$ is necessarily $ CFL$ but $ not$ necessarily $ regular$

b. $ R$ is necessarily $ regular$ but $ infinite$

c. $ R$ is necessarily $ non$ $ regular$

d. $ None$

e. $ \phi$


Now I have approached this problem in 2 ways and I am getting 2 different results.


The first way in which I have approached is that, since $ A’-B=A’\cap B’$ , so it is $ Reg$ $ L$ $ \cap$ $ CSL=CSL$ , so answer is $ NONE$


On the other hand I have think of it like this, since $ A$ is $ Regular$ it’s complement is also $ regular$ , Now we know that

enter image description here

So $ regular$ $ language$ being a subset of $ CFL$ must give us $ \phi$ when we are doing $ A’-B$ , so this time I am getting $ \phi$ as answer


My question is which of my approach is correct? Is the first one correct? If so, then why the second one is wrong?

Or is the second one correct? If so then why the first one is wrong?


I believe that the second method shown by me is wrong as say we have a regular language  $ A=\phi$ , so $ \overline{A}=\sum^*$ and say $ B=a^nb^n$

then $ \overline{A}-B=a^xb^y$ , where $ x\neq y$ , so it is a $ CFL$ but not $ \phi$ .

So where did I went wrong in my second proof using $ Chomsky$ $ hierarchy?$


Downvoters(if any) please mention the reason of downvote in comment. Thank you.

What’s the difference between phi and lambda in regular expression?

I’ve been learning on Formal Languages and Automata of Peter Linz(6th edition).

in the chapter 3 of this book, it explains the primitive regular expression.

but I don’t know what is the difference between $ \phi$ and $ \lambda$ .

of course, I know $ \lambda$ means the empty string, so that $ \lambda s=s\lambda$ .

and the textbook explains the meaning of $ \phi$ is the empty set.

and more, the textbook explains that $ \phi$ can be accepted by a deterministic finite automata $ \left< Q, \Sigma, \delta, q_0 , F \right>$ in which $ Q=\{ q_0, q_1 \}$ , $ \forall a \in \Sigma:\delta(q_0,a)\text{ is not defined}$ , and $ F=\{q_1\}$ .

so, I guess the meaning of the $ \phi$ is the rejected string.

but How can the expression $ (\phi *)*$ mean $ \lambda$ ?

and what’s the meaning of the expression $ a\phi$ ?

Proving sets of regular expressions and context free grammars are decidable [duplicate]

This question already has an answer here:

  • What is the complexity of deciding if the intersection of a regular language and a context free language is empty? 1 answer
  • Intersection between regular language and context-free language [closed] 1 answer
  • Proof Idea: How to prove the intersection of regular language and CFL is a CFL? 2 answers
  • Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL? 4 answers
  • Intersection of context free with regular languages 1 answer

Consider below languages:

  1. $ L_1=\{<M>|M$ is a regular expression which generates at least one string containing an odd number of 1’s$ \}$
  2. $ L_2=\{<G>|G$ is context free grammar which generates at least one string of all 1’s$ \}$

Its given that both above languages are decidable, but no proof is given. I tried guessing. $ L_1$ is decidable, its a set of regular expressions containing

  • odd number of $ 1$ ‘s, or
  • even number of $ 1$ ‘s and $ 1^+$ or
  • $ 1^*$

So we just have to parse regular expression for these characteristics. Is this right way to prove $ L_1$ is decidable?

However, can we have some algorithm to check whether given input CFG accepts at least one string of all 1’s? I am not able to come up with and hence not able prove how $ L_2$ is decidable.

Which of the following are regular languages? [duplicate]

This question already has an answer here:

  • How to prove a language is regular? 8 answers

Which of the following are regular?

  1. $ \{a^lb^mc^n|10000>l>m>n\}$
  2. $ \{w| \Sigma=\{a,b,c\},10000>n_a(w)>n_b(w)>n_c(w)\}$ where $ n_x(w)$ is number of $ x$ in $ w$

I feel 1st language is regular, even though we need to compare occurrences of multiple symbols, because there is upper bound of 10000 on the largest number of occurrences of $ a$ . So we might end up with huge NFA having branch for each combination of occurrences of those symbols.

But I am unsure about 2nd language. In this DFA needs to keep count of symbol across word. Or in this also, it is possible with another even larger NFA exhaustively matching different permutation of those symbols across word through different branches each dedicated to different permutation?

Is concatenation of regular language with any other language regular?

I came across following problem:

True or false? If $ L$ is a regular and $ M$ is not a regular language then $ L.M$ is necessarily not regular.

The answer given was:

Consider $ L$ to be $ \emptyset$ and $ M$ be $ \{a^nb^n | n\leq 0\}$
$ L.M=\emptyset$ , which is regular. Hence the statement is false.

I guess the solution incorrectly tries to generalize the case of those two specific languages to all other languages. For example, if $ M$ is DCFL, then I believe $ L.M$ wont be regular. Am I correct with this?

Why LL(1) grammar generate all regular languages?

I came across following:

Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.

I tried to get that.

Definition: Right linear grammar (RLG)
In right linear grammar, all productions are of one of the following forms: $ A\rightarrow t^*V$ or $ A\rightarrow t^*$ , where $ A$ and $ V$ are non terminals and $ t$ is terminal.

Definition: LL(1) grammar

A grammar $ G$ is $ LL(1)$ grammar if and only if whenever $ A→α|β$ are two distinct productions of $ G$ , the following conditions hold:

  1. For no terminal $ a$ do both $ α$ and $ β$ derive strings beginning with $ a$ .
  2. At most one of $ α$ and $ β$ can derive the empty string.
  3. If $ β⇒^*ϵ$ , then $ α$ does not derive any string beginning with a terminal FOLLOW(A). Likewise, if $ α⇒^*ϵ$ , then $ β$ does not derive any string beginning with a terminal in FOLLOW(A). ($ β⇒^*ϵ$ means $ B$ derives $ \epsilon$ )

(Q1.) How definition of RLG ensures condition 1 in the definition of LL(1) grammar.

This answer says:

All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token.

(Q2.) I read somewhere “eliminating left recursion from given grammar does not necessarily make it LL(1)”. Then how turning grammar to right recursive will ensure its LL(1) (as stated in above quoted answer)?

(Q3). I didnt get the significance of “one produces ε and has $ as a lookahead token” in above quoted answer.

(Q4.) First quote in this question says right linear grammar is LL(1). How is it so?

(Q5.) This answer says “all regular languages have a LR(0) grammar”, I guess its incorrect as LR(0) are DCFLs with prefix property which are not superset of regular languages. Am I right with this?

Regular users logs in as ADMIN if Admin logged in recently

Just found a crazy vulnerability and have no idea how to fix it.

Here is a situation:

  1. Admin logs in to a website.
  2. Regular user logs in using their credentials within the next few minutes
  3. Instead of logging in to their profile, they get access to admin resources. Their username is reflected as admin and they have access to all the features.

Why is this happening and how to stop it?

That’s not the first time it happens and I am really concerned about it. I am using optimizepress plugin for creating custom login page. Don’t know if it may be related to the problem

Showing that the class of regular languages are closed under merging / modified shuffle

Consider $ ab$ and $ cd$ which are two words. We merge these two into 6 possibilities: $ abcd, acbd, acdb, cabd, cadb, cdab$

So in general, a merge of words/sequences $ x, y ∈ Σ∗$ , is a word of length $ |x| + |y|$ with both $ x$ and $ y$ as disjoint subsequences in it.

For two languages $ L1$ and $ L2$ their merge is defined as the set of all possible merges of two words $ x ∈ L1, y ∈ L2$ .

So basically, a merge is a modified shuffle and should be of length that of the sum of the length of two languages, and should also be in order (see $ ab$ and $ cd$ example, as $ b$ could not come before $ a$ ).

I was thinking of just connecting the states of all $ L1$ and $ L2$ but this seems wrong as if you connect them all like a fully connected graph, one can jump and go back which is not acceptable.

What’s a basic idea on the construction I could do to prove this?

Simulating these special dice on more regular dice

So I’ve got a game that uses special dice for its resolution. Basically when making an opposed check, each side rolls a bunch of them based on the relevant trait, and whoever rolls most points wins. The margin by which you win matters for resolution, usually.

But I’d like to simulate the resolution on regular dice. (Or rather; I’d like to be able to play, and let others play, without buying more of these special dice).

But I’m stumped because the dice symbols don’t line up easily. Effectively, the special dice are marked [-1, 0, 0, 1, 1, 2] with a minimum score of 0 for any roll.

Because the margin of victory matters, I can’t just replace it with “whoever rolls higher”, and because of the -1 on the die there’s a bigger chance of rolling nothing than normal.

Can anyone see a way to match (or at least get very close) to the resolution mechanic used here, while using easy to get dice? I’m okay with them not being 6-sided, but I would like something with a regular distribution.