Why is a Context Free Grammar that is simultaneously in Chomsky Normal Form and Greibach Normal Form regular?

In my course materials, there is one sentence about how if CFG is in Chomsky Normal Form, it is not regular, and if it is in Greibach Normal form, it also is not. But when a grammar is simultaneously both GNF and CNF, it somehow implies that the grammar is regular – why is it so?

I struggle to understand what would the productions of the grammar that is both in CNF and GNF look like. As in GNF, the production rule is in form: $ A \rightarrow aA_1A_2…A_n$ such that the nonterminal sequence can be empty, I think that the only way a grammar can be in both normal forms, is when the production rules are in form: $ A \rightarrow a$ .

Even if this is the case, why does it imply that the grammar is regular? What is the relationship between regular and context-free grammar?

Is it secure to rely on the data in a lambda context authorizer claims?

I am working on lambda authorization and I learned that there are generally two options.

Either use the default authorizer on the API gateway level, which will do all the heavy lifting (validate the tokens), or write a custom authorizer, which will require me to implement all the logic including all the token validations, which I would like to avoid if possible. I don’t want to write such code, I want to use something that is time proven and tested.

My question is, is it considered secure to write code in my lambda (e.g. python decorator) that will do authorization based on the data in the lambda context.authorizer.claims? assuming of course all I need is there (e.g. cognito:groups, cognito:username, etc.)

can I treat the authorizer data in the context as solid (passed the security validation)?

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.

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.

Calculating effective access time in memory caching context

I have went through various problems involving time required to access required data in the context of caching.

They use different formulae in different problems. For example, this answer suggests these formulae:

effective-access-time = hit-rate * cache-access-time                   + miss-rate * lower-level-access-time    effective-access-time = cache-access-time + miss-rate * miss-penalty 

Let me rewrite them:

  1. $ T_{eff}=H_{L1}\times T_{L1} + (1-H_{L1})\times T_{LowerLevelMemories}$
  2. $ T_{eff}=T_{L1}+(1-H_{L1})\times T_{L1MissPenalty}$

where,
$ H_{L1}$ is L1 cache hit rate
$ T_L1$ is L1 cache access time
$ T_{LowerLevelMemories}$ is time to access lower level memories
$ T_{L1MissPenalty}$ is L1 cache miss penalty

About when to use which formula, the answer says:

  • use first formula when lower level memory access time is given and
  • 2nd formula when miss penalty is given.

Is it so?

Let me put $ T_{LowerLevelMemories}=T_M$ , a main memory access time in formula 1. Also, I feel formula 1 ignores that we do indeed access L1 cache when cache miss occurs. So we should also multiply $ (1-H_{L1})$ by $ T_{L1}$ . So formula 1 becomes:

$ T_{eff}=H_{L1}\times T_{L1} + (1-H_{L1})\times (T_M+T_{L1})$ $ =H_{L1}\times T_{L1} + T_M+T_{L1} -H_{L1}\times T_M-H_{L1}\times T_{L1}$
$ =T_{L1}+(1-H_{L1})\times T_M$

This last equation resembles formula 2 above. Also we can interpret that $ T_M$ is exactly the L1 miss penalty. So I feel, we should

  • use formula 2 when we assume L1 is accessed even during miss and
  • formula 1 when we assume L1 is not accessed during miss

However this does not align with what answer has to suggest as quoted above. Am I correct with how to make decision when to use which formula or the quoted suggestion from the answer is correct?

Is the usage of “wocao” in a context like this genuine? [closed]

In this white paper they use a humorous screenshot as the basis for the code name of an identified attack.

web shell

https://www.fox-it.com/en/news/whitepapers/operation-wocao-shining-a-light-on-one-of-chinas-hidden-hacking-groups/

Knowing that the attackers (presumably APT20) were shown to be extremely competent technically, would the use of this phrase “wocao” taken in isolation be a strong indicator of nationality?

In other articles, I have often seen nation-state actors leave misleading cultural fingerprints.

Regular Expression for a Context Free Language [duplicate]

This question already has an answer here:

  • How to prove that a language is not context-free? 5 answers

I want to know if its possible to write a regular expression for a context free language:

For example I have a language : L={a^n b ^m: n<= m +3}

I have written the following regular expression for it:

a*bbb(b)* 

Is this possible? Somebody please guide me.

Zulfi.

Can there be a context free language that is not recognizable by a PEG?

This is related to this question. Essentially, I want to know whether my reasoning is correct.

  1. We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: Valient 1975, backword: Lee et al. 2002) and it has a lowerbound of O(n^2) for arbitrary matrices.
  2. So there should exist a context free language such that it takes at least O(n^2) time for checking the membership.
  3. PEGs are known to require only linear time (Birman and Ullman 1970), (Loff et al. 2019).
  4. If there exist a PEG for that context free language, it would be a recognizer that checks the membership in linear time, and hence, can solve that matrix multiplication in linear time.

Hence, there does not exist a PEG for that CFL.

Where am I going wrong?